{"raw_statement":[{"iden":"statement","content":"A sum of _p_ rubles is charged from Arkady's mobile phone account every day in the morning. Among the following _m_ days, there are _n_ days when Arkady will top up the account: in the day _d__i_ he will deposit _t__i_ rubles on his mobile phone account. Arkady will always top up the account before the daily payment will be done. There will be no other payments nor tops up in the following _m_ days.\n\nDetermine the number of days starting from the 1\\-st to the _m_\\-th such that the account will have a negative amount on it after the daily payment (i. e. in evening). Initially the account's balance is zero rubles."},{"iden":"input","content":"The first line contains three integers _n_, _p_ and _m_ (1 ≤ _n_ ≤ 100 000, 1 ≤ _p_ ≤ 109, 1 ≤ _m_ ≤ 109, _n_ ≤ _m_) — the number of days Arkady will top up the account, the amount of the daily payment, and the number of days you should check.\n\nThe _i_\\-th of the following _n_ lines contains two integers _d__i_ and _t__i_ (1 ≤ _d__i_ ≤ _m_, 1 ≤ _t__i_ ≤ 109) — the index of the day when Arkady will make the _i_\\-th top up, and the amount he will deposit on this day. It is guaranteed that the indices of the days are distinct and are given in increasing order, i. e. _d__i_ > _d__i_ - 1 for all _i_ from 2 to _n_."},{"iden":"output","content":"Print the number of days from the 1\\-st to the _m_\\-th such that the account will have a negative amount on it after the daily payment."},{"iden":"examples","content":"Input\n\n3 6 7\n2 13\n4 20\n7 9\n\nOutput\n\n3\n\nInput\n\n5 4 100\n10 70\n15 76\n21 12\n30 100\n67 85\n\nOutput\n\n26"},{"iden":"note","content":"In the first example the balance will change as following (remember, initially the balance is zero):\n\n1.  in the first day 6 rubles will be charged, the balance in the evening will be equal to  - 6;\n2.  in the second day Arkady will deposit 13 rubles, then 6 rubles will be charged, the balance in the evening will be equal to 1;\n3.  in the third day 6 rubles will be charged, the balance in the evening will be equal to  - 5;\n4.  in the fourth day Arkady will deposit 20 rubles, then 6 rubles will be charged, the balance in the evening will be equal to 9;\n5.  in the fifth day 6 rubles will be charged, the balance in the evening will be equal to 3;\n6.  in the sixth day 6 rubles will be charged, the balance in the evening will be equal to  - 3;\n7.  in the seventh day Arkady will deposit 9 rubles, then 6 rubles will be charged, the balance in the evening will be equal to 0.\n\nThus, in the end of the first, third and sixth days the balance will be negative in the end of the day."}],"translated_statement":[{"iden":"statement","content":"每天早晨，Arkady的手机账户会被扣除#cf_span[p]卢布。在接下来的#cf_span[m]天中，有#cf_span[n]天Arkady会向账户充值：在第#cf_span[di]天，他会向账户存入#cf_span[ti]卢布。Arkady总是在每日扣款前完成充值。在接下来的#cf_span[m]天内，不会有其他任何扣款或充值。\n\n请计算从第#cf_span[1]天到第#cf_span[m]天中，有多少天在每日扣款后（即傍晚）账户余额为负数。初始时账户余额为0卢布。"},{"iden":"input","content":"第一行包含三个整数#cf_span[n], #cf_span[p]和#cf_span[m]（#cf_span[1 ≤ n ≤ 100 000], #cf_span[1 ≤ p ≤ 109], #cf_span[1 ≤ m ≤ 109], #cf_span[n ≤ m]）——分别表示Arkady会充值的天数、每日扣款金额和需要检查的天数。接下来的#cf_span[n]行中，第#cf_span[i]行包含两个整数#cf_span[di]和#cf_span[ti]（#cf_span[1 ≤ di ≤ m], #cf_span[1 ≤ ti ≤ 109]）——表示Arkady第#cf_span[i]次充值的日期和金额。保证这些日期互不相同且按递增顺序给出，即对所有#cf_span[i]从#cf_span[2]到#cf_span[n]，都有#cf_span[di > di - 1]。"},{"iden":"output","content":"请输出从第#cf_span[1]天到第#cf_span[m]天中，有多少天在每日扣款后账户余额为负数。"},{"iden":"examples","content":"输入3 6 72 134 207 9输出3输入5 4 10010 7015 7621 1230 10067 85输出26"},{"iden":"note","content":"在第一个例子中，余额变化如下（初始余额为0）：\n在第一天，扣除#cf_span[6]卢布，傍晚余额为#cf_span[ - 6]；\n在第二天，Arkady存入#cf_span[13]卢布，然后扣除#cf_span[6]卢布，傍晚余额为#cf_span[1]；\n在第三天，扣除#cf_span[6]卢布，傍晚余额为#cf_span[ - 5]；\n在第四天，Arkady存入#cf_span[20]卢布，然后扣除#cf_span[6]卢布，傍晚余额为#cf_span[9]；\n在第五天，扣除#cf_span[6]卢布，傍晚余额为#cf_span[3]；\n在第六天，扣除#cf_span[6]卢布，傍晚余额为#cf_span[ - 3]；\n在第七天，Arkady存入#cf_span[9]卢布，然后扣除#cf_span[6]卢布，傍晚余额为#cf_span[0]。\n因此，第一天、第三天和第六天结束时余额为负。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, p, m \\in \\mathbb{Z}^+ $:  \n- $ n $: number of top-up days,  \n- $ p $: daily deduction amount,  \n- $ m $: total number of days to check.  \n\nLet $ D = \\{(d_i, t_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the set of top-up events, where:  \n- $ d_i \\in \\{1, \\dots, m\\} $: day of top-up,  \n- $ t_i \\in \\mathbb{Z}^+ $: amount deposited on day $ d_i $,  \nwith $ d_1 < d_2 < \\dots < d_n $.  \n\nLet $ B: \\{1, \\dots, m\\} \\to \\mathbb{Z} $ be the account balance at the end of day $ k $, after the daily deduction.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 100{,}000 $, $ 1 \\le p \\le 10^9 $, $ 1 \\le m \\le 10^9 $, $ n \\le m $.  \n2. $ d_i > d_{i-1} $ for all $ i \\in \\{2, \\dots, n\\} $.  \n3. Initial balance: $ B(0) = 0 $.  \n\n**Balance Evolution**  \nFor each day $ k \\in \\{1, \\dots, m\\} $:  \n- If $ k \\in \\{d_1, \\dots, d_n\\} $, then top-up occurs before deduction:  \n  $$\n  B(k) = B(k-1) + t_i - p \\quad \\text{where } d_i = k.\n  $$  \n- Otherwise:  \n  $$\n  B(k) = B(k-1) - p.\n  $$  \n\n**Objective**  \nCompute:  \n$$\n\\left| \\left\\{ k \\in \\{1, \\dots, m\\} \\mid B(k) < 0 \\right\\} \\right|\n$$","simple_statement":null,"has_page_source":false}