Star Ring Defense

Observations show that there will be a total of n waves of asteroid swarm attacks on the solar system. The i-th wave is described by two parameters: d_i and m_i, meaning that on solar day d_i an asteroid swarm with total mass m_i will appear. If we do not perform a precise defense, the solar system could be doomed. Therefore, you have been assigned the task of building the Star Ring Defense system.

The defense system has the following property: on each solar day it can destroy asteroids of total mass at most k. For an asteroid swarm appearing on day d, the defense must completely destroy its mass during day d or day d+1. (If only a partial destruction is possible or if it is not destroyed within these two days, the remaining asteroid mass will be handed over to the Earth Peace Organization TPC – an outcome you definitely want to avoid!)

Your goal is to determine the maximum total mass of asteroids that the Star Ring Defense system can destroy.

Note on allocation strategy: When an asteroid wave appears on day d, you have two chances (day d and day d+1) to allocate available defensive capacity to it. However, the daily capacity is shared among waves. In particular, if on a day multiple waves require defense (because one wave is in its second chance, and another is today’s new attack) then the sum of the defense allocated on that day cannot exceed k. Also, partial destruction yields no credit; you must allocate a total of m_i (possibly split between the two days) to count the full mass m_i as destroyed.

Hint: One way to think of the problem is to note that every wave i occupies two consecutive days, d_i and d_i+1 – if you decide to destroy that wave you must “pay” a cost of m_i on day d_i and an additional cost of m_i on day d_i+1. However, since you can choose how much of the payment is carried on which day (subject to the daily limit k), the problem reduces to selecting a subset of the waves such that if for every solar day you let X_d be the total mass of waves whose defense occurs on day d, then

X₁ ≤ k, and for each day d ≥ 2, X_d-1 + X_d ≤ k.

The answer is the maximum total mass (i.e. the sum of m_i for the waves chosen) for which such an allocation is possible.

inputFormat

The input begins with two integers n and k separated by a space, where n is the number of asteroid waves, and k is the maximum total mass the defense system can destroy in one day. Following that, there are n lines, each containing two integers d and m (separated by a space) representing a wave that appears on day d with total mass m.

Constraints: You may assume that all numbers are positive integers. It is guaranteed that the input is valid.

outputFormat

Output a single integer – the maximum total mass of asteroids that can be completely destroyed by the Star Ring Defense system.

sample

3 10
1 5
2 7
3 4

9