| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 119 | 103 | 90 | 90.000% |
In the country of milk and honey, Juku is in charge of cows and bees. Since bees will sting cows and make them unhappy and cows will eat all the flowers bees use to make honey, cows and bees need to be kept on separate fields. Each field can support a limited number of animals. Cows and bees are free to obtain, so as many will be put on any field as can be supported there.
Each cow produces one unit of milk and each bee produces one unit of honey. Milk and honey produce different levels of happiness when consumed. Additionally, customers place higher value on "rare" goods. So, when the first unit of milk from a given field produces $M$ units of happiness, the second one only produces $M - D_M$ units, the third one $M - 2 \cdot D_M,ドル and so on (though the values never go below zero). Similar pattern also holds for the value of honey.
Juku's task is to choose how to place cows and bees in the milk and honey land to maximize happiness. Juku needs your help to do this since the calculations are too many to be done on a piece of paper.
The first line of the text file contains two integers: $M$ (0ドル \le M \le 1000$), the amount of happiness of first unit of milk, and $D_M$ (0ドル \le D_M \le M$), the incremental decrease of happiness value for each following unit of milk produced on one field. The second line contains two integers: $H$ and $D_H$ (0ドル \le D_H \le H \le 1000$), giving the same information for honey.
The third line contains $N$ (1ドル \le N \le 1000$), the number of fields. The following $N$ lines describe the fields. Each line contains $C$ (0ドル \le C \le 100$) and $B$ (0ドル \le B \le 100$), the the number of cows and the number bees the fields can support.
The only line of output should contain a single number, the maximum amount of happiness achievable.
3 0 5 0 3 4 2 3 2 2 1
28
The optimal plan is to put cows on the first, bees on the second, and cows on the third field, producing 4ドル \cdot 3 + 2 \cdot 5 + 2 \cdot 3 = 28$ units of happiness in total.
7 4 5 2 3 2 2 1 3 3 1
29
On the first field cows would produce 7ドル + 3 = 10$ units of happiness, while bees would produce 5ドル + 3 = 8$ units. On the second field cows would produce 7ドル$ units, while bees would produce 5ドル + 3 + 1 = 9$ units. On the third field cows would produce 7ドル + 3 + 0 = 10$ units, while bees would produce 5ドル$ units. Thus, the optimal plan is to put cows on the first, bees on the second, and cows on the third field, producing 10ドル + 9 + 10 = 29$ units of happiness in total.
Olympiad > Estonian Informatics Olympiad > 2016-17 > Final Round > Gymnasium 1번