건조기

방금 세탁기에서 꺼낸 젖은 옷이 $n$벌 있다. 전자식 건조기도 하나 있으며, 이 건조기는 한 번의 실행으로 모든 옷을 말릴 수 있을 만큼 크다. 건조용 공기의 온도는 조절할 수 있다. 다만 모든 옷을 높은 온도에서 말리면 일부 옷이 손상된다. 정확히 말하면, $t_i$는 $i$번째 옷을 손상 없이 말릴 수 있는 최고 온도이고, $w_i$는 $i$번째 옷의 젖은 정도이다. 이 옷을 온도 $T$ (단, $T \le t_i$)에서 말리면 $m_i = 30 + (t_i - T) w_i$분이 걸린다. 옷을 두 벌 이상 함께 말리면 건조기가 걸리는 시간은 그중 가장 긴 $m_i$이다. 모든 옷을 손상 없이 말려야 한다.

$n$벌의 옷을 최대 $k$개의 그룹으로 나누고, 그룹마다 건조기를 한 번씩 돌린다. 각 옷의 $t_i$와 $w_i$가 주어졌을 때, 모든 옷을 손상 없이 말리는 데 걸리는 최소 총 시간을 구하라.

그림은 $n = 4$, $k = 2$인 경우를 보여준다. 이때 총 시간은 $90 + 30 = 120$분이다.

첫째 줄에 정수 $n$ ($1 \le n \le 1{,}000$)과 $k$ ($1 \le k \le 3$)이 주어진다. 이후 $n$개의 줄에는 각각 정수 $t_i$ ($40 \le t_i \le 100$)와 $w_i$ ($0 \le w_i \le 100$)가 주어진다.

모든 옷을 손상 없이 말리는 데 걸리는 최소 총 시간을 정수로 한 줄에 출력한다.