워밍업

사샤에게는 편의식품 $n$개가 있다. 먹기 전에 전자레인지로 데워야 한다. 각 음식을 데우는 데 $w_i$초가 걸리고, 먹는 데 $c_i$초가 걸린다. 각 음식에는 준비도 $r_i$가 있으며, 처음에는 $r_i = 0$이다.

$i$번째 음식을 전자레인지에 넣은 뒤에는 꺼낼 때까지 매초 $r_i$가 1씩 증가한다. 전자레인지에는 동시에 한 음식만 들어갈 수 있다. 어떤 경우에도 $r_i$는 $w_i$를 넘어서는 안 된다. 매 $k$초마다, 먹고 있지 않고 전자레인지에도 없는 모든 음식의 $r_i$가 정확히 1씩 감소한다. 다만 $r_i = 0$이면 그대로 둔다. 사샤는 $r_i = w_i$일 때만 음식을 먹기 시작할 수 있고, 먹기 시작한 음식을 다 먹을 때까지 다른 음식은 먹지 않는다.

사샤는 전자레인지 작업과 식사를 동시에 할 수 있다. 음식을 넣거나 꺼내는 데 걸리는 시간은 무시할 만큼 짧다. 다만 이런 작업은 정수 시각에만 할 수 있다. 모든 음식을 다 먹는 데 걸리는 최소 시간을 구하라.

첫 줄에 정수 $n$과 $k$가 주어진다 ($1 \le n \le 10$, $1 \le k \le 10^3$).

다음 $n$개 줄에는 각각 정수 $w_i$와 $c_i$가 주어진다 ($1 \le w_i, c_i \le 10^3$).

사샤가 모든 음식을 다 먹는 데 걸리는 최소 시간을 정수 하나로 출력한다.