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