Andy is exploring how toys impact a person's happiness level in his psychology class. He recruited a study participant named Jamie.
Jamie can select toys from the store to be his birthday gifts, and he can exchange toys with his friends. There are types of toys.
For the toy , Jamie can select at most of it from the store, and it has a base happiness value of . However, if Jamie owns multiple of the same toy, the happiness value Jamie gets from it decreases: the second toy will only give him of happiness, the third toy will give him of happiness, and the toy will give him of happiness. Note that if the happiness value is a decimal, it will be rounded down to the nearest integer.
Jamie has friends. His friend, where , has an infinite amount of toy and is willing to exchange one of his toy with one of Jamie's toy , but Jamie will lose happiness in the process. It is worth noting that Jamie can refuse an exchange or repeat an exchange as many times as he wants as long as he has the appropriate toy for exchange.
You need to find the maximum amount of happiness Jamie can achieve after some (possibly zero) exchanges.
Constraints
For all subtasks:
Subtask 1 [15%]
Subtask 2 [85%]
No additional constraints.
Input Specification
The first line contains three integers , , and .
The following lines contain two integers and .
The following lines contain three integers , , and .
Output Specification
Output an integer that represents the maximum sum of happiness value Jamie can achieve.
Sample Input
4 5 2
100 1
20 2
30 1
200 0
10 4
5 4 150
3 2 5
Sample Output
200
Sample Explanation
Jamie selects one of each toy from the store and exchanges his toy with his first friend's toy .
Comments