| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1136
Packing Biscuits
Time Limit: 1000ms
Memory Limit: 65536kb Description
You may have read the problem “Crazy Biscuits”, here is what the next day will happen.
Dango baked some biscuits this evening. It’s Mars time 1:00am now, but she keeps herself sober for the purpose-tolerably sober. She has put the biscuits into some delicate boxes but now she’s got no idea. There is a sequence of N biscuits on the table. They are numbered from 1 to N. The sequence of biscuits must be put into one or more boxes, where each box contains consecutive jobs in the sequence. Those biscuits and boxes are weird. The size of an empty box is B. The total size of a box equals to the sum of the sizes of all the biscuits in it. Notice that empty box doesn’t increase happiness index around the house, although she has unlimited boxes. Each biscuit has its own size Si and happiness value Vi. Now, let’s look at the i-th biscuit and we assume that this biscuit is in the j-th box(the first box is numbered 1). This biscuit would increase the total happiness index around the house of Happyi. Happyi = Hi*(Total size of box 1 + Total size of box 2 + … + Total size of box j) Here is an example. The size of an empty box is 1, and Dango has 4 biscuits. S = {2, 3, 4, 5}. H = {6, 7, 8, 9}. If you put them into boxes like this: {1,2,3}, {4}, the happiness index around the house should be calculated like this: T_size1 (The total size of box 1) = B + S1 + S2 + S3 = 1 + 2 + 3 + 4 = 10. T_size2 (The total size of box 2) = B + S4 = 1 + 5 = 6. The happiness index around the house = H1*T_size1 + H2*T_size1 + H3*T_size1 + H4*( T_size1+T_size4) = 6*10 + 7*10 + 8*10 + 9* (10+6) = 354. Dango wants to have the minimum happiness index around the house after handling these biscuits and boxes (If people on Mars think she is a noodle, they will send her back to earth. She really wants to go come), but she is not good at problem complicated like this. Can you help her? Input
The first line contains an integer T(1<=T<=25), which means the input consists T test cases.
For each test case, the first line contains the number of jobs N, 1 <= N <= 10000. The second line contains size B of a box which is an integer(0 <= B <= 50). The following N lines contain information about the biscuits. First on each of these lines is an integer Si, 1 <= Si <= 100, the size of the biscuit. Following that, there is an integer Hi, 1 <= Hi <= 100, the happy value of the biscuit. Output
For each test case you should output the minimum happiness index around the house like this: Case #x: xxx. (There are only two spaces in the line. The first space is between “Case” and “#” in the line, the second is after “:” )
Sample Input
2 2 50 100 100 100 100 4 1 2 6 3 7 4 8 5 9 Sample Output
Case #1: 45000 Case #2: 319 |