Bosco has gotten his hands on 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 cards for sale. Card costs dollars. and will improve Bosco's DQI (Deck Quality Index) by 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 days of the sales. In fact, he's already acquired a list of the price adjustments that will be made.

On day , the cost of card is changed to , while all other cards remain unchanged. That is, before day , all cards have their initial costs , 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 , only cards from to , 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 days, he wants to buy some (possibly empty) set of cards, such that the sum of their costs is no larger than , 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 Specification

Line : The integers , , and .

The next lines: The integers and .

The next lines: The integers , , and .

#### Output Specification

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
```

#### Sample Output

```
22
10
25
```

#### Explanation for Sample Output

At first, the cards (with point values , , , , and ,
respectively) have costs of , , , , and dollars, in that order.

On the first day, the cost of the first card is reduced to dollar, and
the first cards are up for purchase.

On the second day, the cost of the fourth card is increased to
dollars, and only the last cards can be bought.

On the final day, the cost of card is changed again, this time to
dollar, and the first cards are once again considered.

On the first day, Bosco should buy the first, second, and fourth cards,
costing a total of dollars.

On the second, cards and should be purchased for dollars, as card
is now too expensive.

On the final day, all of the cards up for sale can be bought for
dollars. Notice that card still costs dollar, from the first price
change.

## Comments

It appears that the data satisfies as opposed to .