All submissions for this problem are available.
Aakash is the number one foodie of USICT and he loves to eat a lot. On his birthday his friends wanted to give him the best feast he ever had. So they took him to restaurant and ordered N number of dishes.
Initially his hunger is 0, as the time passes the hunger of Aakash increases by K ounces per second(i.e he can eat K ounces after 1 sec, K more after another second and so on). Now at end of certain time T[i] seconds, dish weighing D[i] ounces arrives.Aakash can reject this dish if he wants, but Aakash can only eat this dish if his hunger is greater than or equal to the D[i] and D[i] will be subtracted from his current hunger. Else he has to reject the dish, the dish is thrown away and nothing is reduced from his current hunger.
Aakash wants to eat maximum number of dishes
so he asks for your help. Help him figure out the maximum number of dishes he can eat.
Note : Aakash will eat the dish completely, so no partial eating and whole weight of the dish is reduced for his hunger.
First Line consists of a single integer N - number of dishes.
Next N lines consists of T[i] and D[i] - arrival time of a dish and it weight.
All T[i] are distinct.
Last line consists of a single integer K - the rate at which Aakash's hunger increases.
Output a single integer , telling the maximum number of dishes Aakash can eat.
Subtask 1 :
1 <= N <= 1000
1 <= T[i] , D[i] <= 1000
1 <= K <= 10^7
1 <= N <= 500000
1 <= T[i] , D[i] <= 10^9
1 <= K <= 10^7
Sample input 1 :
Sample output 1 :
Aakash can eat maximum 4 dishes. Aakash cannot eat the dish arrived at T[i] = 2 with D[i]=3 as his current hunger is 2 while the weight of the dish is 3, rest he can eat all 4 dishes afterwards.
Sample input 2 :
Sample output 2:
Aakash cannot eat any of the dishes as his hunger is always less than the D[i] at corresponding T[i].
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions