这是一道热身题。

Sasha 有 $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$，此时它保持不变。Sasha 只有在 $r_i = w_i$ 时才能开始食用某份菜肴，并且在吃完当前菜肴之前，他不会去吃任何其他菜肴。

Sasha 非常擅长多任务处理，因此他可以同时操作微波炉和进食，并且放入或取出菜肴的时间可以忽略不计。但他不是超人，所以他只能在整数时刻进行这些操作。Sasha 喜欢吃东西，但他不喜欢花费太多时间。你需要确定 Sasha 吃完所有菜肴所需的最短时间。

输入格式

第一行包含两个整数 $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$)。

输出格式

输出一个整数，表示 Sasha 吃完所有菜肴所需的最短时间。

样例

输入 1

3 3
5 3
6 3
1 2

输出 1

15