시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 119 | 80 | 70 | 67.961% |
"There is probably a place where all waiters have a PhD in, I don't know, some stuff." - Dudu, 2014
Note: This problem is identical to Small PhD Restaurant, but with larger bounds.
Dudu is hungry. He sat down in a nice Thai restaurant. To his amazement, he realized that he is in the PhD restaurant, a wonderful place where every staff member has a PhD in some stuff.
Even more, each staff member has arranged a challenge related to his or her field of study for Dudu to attempt while he waits for his food. The challenge arranged by staff member i costs Ai to attempt and will award Dudu Biwhen he completes it successfully.
Each challenge can be completed at most once and they can be attempted in any order. Dudu is very smart and can complete any challenge, but he must have enough money to pay Ai before he attempts challenge i. If Dudu starts with M money, determine the maximum amount he can obtain.
Input begins with a line containing two integers N and M, the number of challenges and the amount of money Dudu begins with, respectively.
The following line contains N numbers A1,A2, ..., AN, indicating the costs to attempt each challenge.
Finally, the last line contains the N numbers B1, B2, ..., BN indicating the payoff from each challenge.
Output a single integer indicating the maximum amount of money Dudu can obtain.
5 100 40 80 50 200 110 20 90 70 300 150
170
Dudu starts with 100 money. He can proceed in the following way: