Ladder

There is a rectangular building with several floors. The horizontal length of the building is the same on every floor, and each floor has one bar. Bar lengths may differ from floor to floor. At time 0, all bars start moving at the same time, either from left to right or from right to left. Time advances in integer units 0, 1, 2, ..., and every bar moves by length 1 per unit time.

At time 0, each bar touches either the left wall or the right wall of the rectangle. A bar keeps moving in its given direction. Whenever one of its ends touches the left wall or the right wall, it immediately reverses direction and continues moving.

Figure 1. Initial state at time 0

Cheolsu initially stands on the bar on the lowest floor. He may move according to the following two rules.

Rule 1) On the bar where he currently stands, he may move to any position on that bar without spending time.

Rule 2) If moving vertically upward from some position on his current bar lands inside the interval of the bar on the floor immediately above, including both endpoints, he may climb to that bar without spending time.

For example, in Figure 2 below, at time 2 he can pass the second floor and move to the bar on the third floor. In Figure 3, at time 4 he can pass the fourth floor and reach the bar on the fifth floor.

Figure 2. Time 2

Figure 3. Time 4

Starting from the initial state at time 0, find the minimum time needed for Cheolsu to climb from the bar on the lowest floor to the bar on the highest floor.

The first line contains the number of floors N and the horizontal length L of each floor. The lowest floor is floor 1, and the highest floor is floor N.

Among the next N lines, the i-th line contains the length l of the bar on floor i and its initial movement direction d. If d = 0, the bar initially touches the left wall and moves to the right. If d = 1, the bar initially touches the right wall and moves to the left.

The constraints are as follows.

• 1 ≤ N ≤ 3,000
• 1 ≤ L ≤ 3,000, and L is even
• 1 ≤ l ≤ L, and l is even
• d is 0 or 1

Output one integer: the minimum time needed for Cheolsu to climb from the bar on the lowest floor to the bar on the highest floor.