Break the Barrier

In a mystical realm connecting ancient and modern worlds, two heroes stand before a towering yet incomplete wall. This wall is built from several groups of consecutive magic bricks, where each brick is a $1\times1\times1$ cube. In each group the bricks all share the same height, and importantly, the heights of different groups are all distinct.

Legend has it that only if there exists a contiguous segment of at least $K$ bricks with the same height can one break through the wall and summon divine help to cross the boundaries of time and space. The heroes can change the wall by performing two types of operations on any brick:

• Remove one brick from the wall (thereby decreasing the height of that position by 1).
• Add one brick from an infinite supply, increasing the height by 1.

Each operation costs 1 unit of energy. Given that the heroes wish to conserve their energy, your task is to compute the minimum energy required so that there exists at least one contiguous segment of $K$ bricks all having the same height.

The wall is given in groups. The first line of input contains two integers $G$ and $K$, where $G$ is the number of groups and $K$ is the required minimal length of a contiguous segment with equal height. Then follow $G$ lines. Each of these lines contains two integers $L$ and $H$, where $L$ denotes the number of bricks in that group and $H$ denotes the height of every brick in that group. Groups are given in order and the wall is formed by concatenating them.

inputFormat

The first line contains two integers $G$ and $K$, where:

• $G$ is the number of groups that form the wall.
• $K$ is the minimum required length of a contiguous segment with identical brick heights.

Then, $G$ lines follow. Each line contains two integers $L$ and $H$, where:

• $L$ is the number of bricks in that group.
• $H$ is the height of the bricks in that group.

It is guaranteed that all group heights $H$ are distinct.

outputFormat

Output a single integer representing the minimum energy required to modify the wall so that there exists at least one contiguous segment of $K$ bricks with the same height.

sample

3 3
2 1
3 3
1 2

0