H - Good Celebration

The ACM-ICPC World Finals are over! Which team came out on top? Why, only our favourite team - everyone's favourite team - the most deserving, lovable, courteous, powerful, flawless, successful team that has ever existed. Who else?

It's time to celebrate, and what better way is there to celebrate than by eating cake? The contest organizers have bought N (1 ≤ N ≤ 200) cakes (conveniently numbered 1..N) - however, ever generous, The Team will only eat cake 1, leaving the rest for the other, inferior teams. They will need their cake to be as tasty as possible, though. To help with this, M (0 ≤ M ≤ 200) globs of icing are available, which will be distributed among the cakes. Icing is always used in whole globs.

The cakes are arranged in a somewhat strange way - piled on top of one another. Cake 1 is directly on top of a table, while every other cake i (for i = 2..N) is directly on top of cake c_i. c₁ is considered to have a value of 0. Note that there may be multiple cakes on top of a single cake, and that the entire structure obeys the laws of physics (no cake is on top of itself, and no cakes are floating).

Now, the tastiness of any cake i is determined by the formula b_i + m_i(x_i + y_i). b_i (0 ≤ b_i ≤ 100) and m_i (0 ≤ m_i ≤ 100) are simply properties of cake i, which depend on its size, shape, weight, temperature, fluffiness, and so on. x_i is the number of globs of icing that are chosen to be applied to cake i. If there are no cakes on top of cake i, y_i = 0 - otherwise, y_i is the minimal tastiness of any cake directly on top of cake i. No cake will ever be capable of achieving a tastiness value larger than 2⁶⁰, no matter how the icing is distributed.

The members of The Team have already, of course, determined how the available icing could be optimally applied to the mountain of cakes to maximize the tastiness of their cake (cake 1). However, the contest organizers are the ones who will actually be distributing the icing, and they had better hope they get it right! Can you help them determine how tasty cake 1 should be? You don't want to know what The Team will do if their celebration isn't perfect…

Input

First line: 2 integers, N and M
Next N lines: 3 integers, c_i, b_i, and m_i, for i = 1..N

Output

1 integer, the maximal tastiness of cake 1, after all of the icing has been used

Sample Input

3 2
0 5 1
1 3 4
1 2 6

Sample Output

12

Explanation of Sample

The optimal icing distribution is 1 glob each on cakes 2 and 3. This gives cake 2 a tastiness of 3 + 4(1 + 0) = 7, and cake 3 a tastiness of 2 + 6(1 + 0) = 8. Since both of these cakes are on top of cake 1, it then has a tastiness of 5 + 1(0 + min(7, 8)) = 12. No other icing distribution yields a higher tastiness for cake 1.

All Submissions
Best Solutions

Point Value: 25
Time Limit: 4.00s
Memory Limit: 64M
Added: Jul 27, 2012
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)