17524번 - Dryer 다국어

You have n wet clothes you just pulled off the washer. You also have an electronic dryer. The dryer is large enough to dry all the clothes in one run. You can control the temperature of the drying air. However, if you dry all the clothes at a high temperature, some clothes will be damaged. Precisely, let t_i denote the highest temperature at which the i-th cloth can be dried without damage and let w_i denote the wetness of the i-th cloth. If you dry this cloth at the temperature T (of course, T ≤ t_i), it will take m_i = 30 + (t_i − T) w_i minutes. If you dry two or more clothes at once, the time the dryer takes is the longest m_i of these clothes. You should dry all the clothes without damage.

Because the dryer uses a lot of electricity, you are going to partition n clothes into at most k groups and runs the dryer for each group. Given n clothes with t_i’s and w_i’s, write a program to find the minimum total time to dry all the clothes without damage.

This figure illustrates an example of n = 4, k = 2. In this case, the total time is 90 + 30 = 120 minutes.

Your program is to read from standard input. The first line contains two integers n (1 ≤ n ≤ 1,000) and k (1 ≤ k ≤ 3). In the following n lines, the i-th line has two integers t_i (40 ≤ t_i ≤ 100) and w_i (0 ≤ w_i ≤ 100).

Your program is to write to standard output. Print exactly one line containing the minimum total time as an integer.