### COCI 2009/2010, Contest #3

## Task RAZGOVORI

Mirko's village has only one long street stretching from east to west with **M** houses. Each house has a unique house number, starting with 1 and ending with **M**.

A recent storm took out most phone lines, so the mayor financed the construction of a new one. Mirko is interested in the popularity of this new phone network, so he infiltrated its construction and placed special detectors on some points.

Detectors detect **any** phone call made between two houses, as long as one of them is eastward and the other is **westward** from the point the detector is installed.

At the end of the first month, Mirko removed all detectors and now wonders what is the **smallest number** of phone calls that could have been made during that month.

### Input

The first line of the input contains two integers, **N** (1 ≤ **N** ≤ 100 000), the number of detectors, and **M** (**N** < **M** ≤ 1 000 000 000), the number of houses in the village.

The next **N** lines contain two numbers each: **P _{i}** (1 ≤

**P**<

_{i}**M**), and

**C**(1 ≤

_{i}**C**≤ 1 000 000 000), the position and total number of phone calls detected by detector number

_{i}**i**. We say that a detector is on position

**P**if and only if he is between houses numbered

_{i}**P**and

_{i}**P**.

_{i}+1**There will never be more than one detector at the same position.**

### Output

Output a single integer, the minimal number of phone calls made.

### Grading

In test cases worth 50% of the points, **N** and **C** will be smaller than 1 000.

### Sample Tests

## Input3 4 3 1 2 2 1 1 ## Output2 |
## Input2 3 1 23 2 17 ## Output23 |
## Input3 9 7 2 8 3 3 4 ## Output5 |

All Submissions

Best Solutions

**Point Value:** 10 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 32M

**Added:** Jul 02, 2013

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...