e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Olympiad

Olympiad

n teams arrived to the Informatics Olympiad. Each team consists of ai boys and bi girls (1in). The participants can live in rooms with m places in each. Find the minimum number of rooms needed to accommodate all the Olympiad participants, if the boys can't be settled with the girls.

Input

The first line contains the values of n and m. In the next n lines the pairs of numbers ai, bi (1in) are given. All numbers are positive integers not greater than 100.

Output

Print the minimum required number of rooms.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2 3
2 1
3 2 
Output example #1
3