Subin and the Melting Candy

Interview

Time limit1sMemory limit64 MB

Summary

Starting at the origin and moving only right or up, visit baskets over time to maximize total candies collected, where a basket's candies shrink by one per time unit.

Level: Medium7 of 10
Topics: Dynamic programming, Sorting
Solved: No attempts yet

Problem

Subin is sitting on the coordinate plane. "I love the coordinate plane so much!!" said Subin. The plane has $N$ candy baskets, and each basket holds $M$ candies. The baskets are at $(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)$ , and Subin starts at $(0, 0)$ .

The weather is hot today. Each time $1$ unit of time passes, one candy melts away from every basket that still has candy left. After $t$ units of time have passed, a basket holds $\max(0, M - t)$ candies.

Subin is very hungry, so when he reaches a basket he eats all the candies in it instantly. Eating takes no time. When Subin moves a distance of $1$ , $1$ unit of time passes. Subin can move only up (the direction in which the $y$ coordinate increases) or right (the direction in which the $x$ coordinate increases).

Write a program that finds the maximum number of candies Subin can eat.

Input

The first line contains $N$ and $M$ .

Each of the next $N$ lines contains the position $x_i$ , $y_i$ of one candy basket. ( $0 \le N \le 300$ , $1 \le M \le 10^6$ , $0 \le x_i, y_i \le 300$ )

No two candy baskets share a position, and there is no candy basket at $(0, 0)$ .

Output

Print the maximum number of candies Subin can eat.

Examples2

Example 1
Input
```
3 15
1 1
3 1
1 6
```
Expected output
```
24
```
Example 2
Input
```
2 3
0 1
2 2
```
Expected output
```
2
```