Dryer
면접 대비시간 제한1초메모리 제한512 MB
n개의 옷을 최대 k개의 그룹으로 나누어 건조할 때, 각 그룹을 온도 T로 건조하면 30 + (ti - T) * wi의 최댓값이 걸린다. 전체 건조 시간의 최솟값을 구한다.
문제
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 ti denote the highest temperature at which the i-th cloth can be dried without damage and let wi denote the wetness of the i-th cloth. If you dry this cloth at the temperature T (of course, T ≤ ti), it will take mi = 30 + (ti − T) wi minutes. If you dry two or more clothes at once, the time the dryer takes is the longest mi 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 ti’s and wi’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 ti (40 ≤ ti ≤ 100) and wi (0 ≤ wi ≤ 100).
출력
Your program is to write to standard output. Print exactly one line containing the minimum total time as an integer.