18615번 - Warm Up 다국어채점 준비 중

This is a warm up problem.

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. Let us introduce parameter r_i of each dish which represents its readiness.

Initially, r_i = 0. After 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 of time. It is dangerous to overheat dishes, so r_i must not exceed w_i under any circumstances. Every k-th second all dishes which 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 remains unchanged. Sasha may start eating a particular dish only if r_i = w_i, and he won’t eat any other dish until he finishes the one he started.

Sasha is pretty capable in multi-tasking, so he may deal with the microwave and eat at the same time, and place dishes to microwave or pull them out in negligibly small amount of time. But he is no superman, so he may do it only in integer moments of time. Sasha likes eating, but he doesn’t like spending too much time on it. You need to determine the minimum amount of time it would take Sasha to finish eating all dishes.

The first line of input contains two integers n and k (1 ≤ n ≤ 10, 1 ≤ k ≤ 10³).

Each of the next n lines of input contain two integers w_i and c_i (1 ≤ w_i, c_i ≤ 10³).

Output a single integer representing the minimum amount of time Sasha would need to finish eating all dishes.