Warm Up

Sasha has $n$ convenience food dishes. He has to warm them up in the microwave before eating. Each dish takes $w_i$ seconds to be warmed up and $c_i$ seconds to be consumed. Each dish has a readiness $r_i$, which starts at $r_i = 0$.

After the $i$-th dish is placed in the microwave, its $r_i$ increases by 1 every second until the dish is pulled out. The microwave can contain at most one dish at any moment. $r_i$ must never exceed $w_i$ under any circumstances. Every $k$-th second, all dishes that are not being eaten and are not in the microwave have their $r_i$ decreased by exactly 1, unless $r_i = 0$, in which case it stays the same. Sasha may start eating a dish only if $r_i = w_i$, and he will not eat any other dish until he finishes the one he started.

Sasha can operate the microwave and eat at the same time. Placing a dish in or pulling it out takes a negligibly small amount of time. He may do these actions only at integer moments of time. Find the minimum total time Sasha needs to finish eating all dishes.

The first line contains two integers $n$ and $k$ ($1 \le n \le 10$, $1 \le k \le 10^3$).

Each of the next $n$ lines contains two integers $w_i$ and $c_i$ ($1 \le w_i, c_i \le 10^3$).

Print a single integer, the minimum amount of time Sasha needs to finish eating all dishes.