Sales

Bosco has gotten his hands on B (1 ≤ B ≤ 50) dollars! Being a Magic the Gathering™ enthusiast, he wishes to spend some amount of his budget on cards to improve his deck.

He has located a local store that has N (1 ≤ N ≤ 30,000) cards for sale. Card i costs c_i (1 ≤ c_i ≤ 50) dollars. and will improve Bosco's DQI (Deck Quality Index) by v_i (1 ≤ v_i ≤ 1000) points. Only one copy of each card is for sale.

Business hasn't been too great lately, so the store is offering sales on various days. Though the term "price adjustments" would be more accurate, as card prices can increase, "sales" are much more appealing - and, indeed, Bosco wants to go do all of his shopping on one of the D (1 ≤ D ≤ 3000) days of the sales. In fact he's already acquired a list of the price adjustments that will be made.

On day i, the cost of card a_i (1 ≤ a_i ≤ N) is changed to b_i (1 ≤ b_i ≤ 50), while all other cards remain unchanged. That is, before day 1, all cards have their initial costs (c), and from then on, price adjustments accumulate from day to day.

Additionally, on each day, only certain cards from the store's inventory are actually up for sale. In particular, on day i, only cards from x_i to y_i (1 ≤ x_i ≤ y_i ≤ N), inclusive, may be purchased.

Bosco doesn't care how much of his budget he spends, but he absolutely must have the best possible deck. As such, for each of the D days, he wants to buy some (possibly empty) set of cards, such that the sum of their costs is no larger than B, and the sum of their DQI points is maximal. Determine the DQI sum for each day, so that Bosco will know when to go to take full advantage of the "sales".

Input

Output

For each day, output the maximal DQI sum of cards up for purchase that day which Bosco can purchase without going over his budget, considering all prices changes that have occurred so far.

Sample Input

5 5 3
9 6
1 5
2 3
3 11
2 7
1 1 1 4
4 6 3 5
4 1 1 4

Explanation

At first, the 5 cards (with point values 6, 5, 3, 11 and 7, respectively) have costs of 9, 1, 2, 3, and 2 dollars, in that order.
On the first day, the cost of the first card is reduced to 1 dollar, and the first 4 cards are up for purchase.
On the second day, the cost of the fourth card is increased to 6 dollars, and only the last 3 cards can be bought.
On the final day, the cost of card 4 is changed again, this time to 1 dollar, and the first 4 cards are once again considered.

Sample Output

22
10
25

Explanation

On the first day, Bosco should buy the first, second, and fourth cards, costing a total of 5 dollars.
On the second, cards 3 and 5 should be purchased for 4 dollars, as card 4 is now too expensive.
On the final day, all of the cards up for sale can be bought for 5 dollars. Notice that card 1 still costs 1 dollar, from the first price change.

All Submissions
Best Solutions

Point Value: 30 (partial)
Time Limit: 1.00s
Memory Limit: 16M
Added: Jun 26, 2010
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Because Jacob is a nitch and wants Ammar to fail, the test data size has been increased. N can now be up to 30000 and D up to 3000. This is reflected in the problem statement.

These should've been the limits in the first place, I had just been too lazy to check whether a solution such as Ammar's would run in time.

Now, I believe the only way to solve it fully is the "intended" way - which happens to connect to a topic Brian has recently taught in PEG.

Also, because I don't like bad HTML, the entire problem statement has been converted to image format, except for the sample input. Enjoy xD

So we are suppose to calculate the maximum DQI for each day?
And also for the second line of input, shouldn't it be '2 6' rather than 
'9 6'?

Yes, for each day (given the range of cards up for sale, and the price changes so far). The initial cost of the 1st card should be 9 dollars - the first sentence of the Explanation will be fixed accordingly.