本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1337. G. Mowing Mischief


Description

Bessie's younger cousins, Ella and Bella, are visiting the farm. Unfortunately, they have been causing nothing but mischief since they arrived.
In their latest scheme, they have decided to mow as much grass as they can. The farm's prime grassland is in the shape of a large t×t square. The bottom-left corner is (0, 0), and the top-right corner is (t, t). The square therefore contains (t+1)2 lattice points (points with integer coordinates).
Ella and Bella plan to both start at (0, 0) and run at unit speed to (t, t) while each holding one end of a very sharp and very stretchy wire. Grass in any area that is swept by this wire will be cut. Ella and Bella may take different paths, but each path consists of only upward and rightward steps, moving from lattice point to lattice point.
Bessie is rather concerned that too much grass will be cut, so she invents a clever plan to constrain the paths Ella and Bella take. There are n yummy flowers scattered throughout the grassland, each on a distinct lattice point. Bessie will pick a set of S flowers that will be required for both Ella and Bella to visit (so Ella's path must visit all the flowers in S, and so must Bella's
path). In order to add as many waypoints to these paths as possible, Bessie will choose S to be as large as possible among subsets of flowers that can be visited by a cow moving upward and rightward from (0, 0) to (t, t).


The Problem:
Ella and Bella will try to minimize the amount of grass they cut, subject to the restriction of visiting flowers in S. Please help Bessie choose S so that the amount of grass cut is as small as possible.

Input

The first input line contains two positive integers: n (1 ≤ n ≤ 2(10)5), indicating the number of yummy flowers scattered throughout the grassland and t (1 ≤ t ≤ 106), where (t, t) are thecoordinates of the top right corner of the grid. Each of the next n lines contains the integer coordinates (xi, yi) of a flower, with 1 ≤ xi, yi ≤ t-1, for all i (1 ≤ i ≤ n), and no two flowers lie on the same horizontal or vertical line.

Output

Output a single integer on a line by itself giving the minimum possible amount of cut grass.

Samples

Input Copy
5 20
19 1
2 6
9 15
10 3
13 11
Output
117

Hint

Sample Explanation:
In this sample, it's best to pick the flowers at (10, 3) and (13, 11). With this selection, the first rectangle of grass cut has dimensions 10 x 3, the second one has 3 x 8, and the last one has the dimensions 7 x 9. The total area of these rectangles is 30 + 24 + 63 = 117. A sub-optimal choice would be taking the flowers at (2, 6) and (9, 15). This choice cuts a rectangle of size 2 x 6, a
second rectangle of size 7 x 9 and a third rectangle of size 11 x 5 for a total area of 12 + 63 + 55 = 130, which is greater than 117. The third possible choice which is sub-optimal would be to pick the flower at (2, 6) and the flower at (13, 11), which results in a total area of grass cut of 152 units2.

Source

UCF2019 PRACTICE
Problem Information

Time Limit: 2000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1037. UCF 2019 Practice
My history solutions

You didn't submit any solution!
Submit your solution

Login Register