SP14864 SALES - Sales

Bosco has gotten his hands on $ B $ ( $ 1 \leq B \leq 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 \leq N \leq 30,000 $ ) cards for sale. Card $ i $ costs $ c_i $ ( $ 1 \leq c_i \leq 50 $ ) dollars, and will improve Bosco’s DQI (Deck Quality Index) by $ v_i $ ( $ 1 \leq v_i \leq 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 \leq D \leq 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 \leq a_i \leq N $ ) is changed to $ b_i $ ( $ 1 \leq b_i \leq 50 $ ), while all other cards remain unchanged. That is, before day $ 1 $ , all cards have their initial costs ( $ c_{1..N} $ ), 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 $ x_i $ to $ y_i $ ( $ 1 \leq x_i \leq y_i \leq 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 consider buying 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 this DQI sum for each day, so that Bosco will know when to go to take full advantage of the “sales”.

Line $ 1 $ : 3 integers, $ B $ , $ N $ , and $ D $ Next $ N $ lines: 2 integers, $ c_i $ and $ v_i $ , for $ i=1..N $ Next $ D $ lines: 4 integers, $ a_i $ , $ b_i $ , $ x_i $ , and $ y_i $ , for $ i=1..D $

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 price changes that have occurred so far.