시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 0 0 0 0.000%

문제

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, Tti), it will take mi = 30 + (tiT) 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.

예제 입력 1

4 2
50 20
70 3
90 10
95 1

예제 출력 1

120

예제 입력 2

4 2
50 20
70 3
90 1
95 1

예제 출력 2

85

예제 입력 3

1 3
40 4

예제 출력 3

30