Roller Coaster Design

Anna works at an amusement park and is responsible for constructing a new roller coaster track. She has designed n special segments (numbered from \(0\) to \(n-1\)). Each segment \(i\) has two properties:

• When entering segment \(i\), the coaster's speed must be no more than \(s_i\) km/h.
• When leaving segment \(i\), the coaster's speed becomes exactly \(t_i\) km/h regardless of its entering speed.

The final design is a single roller coaster track that arranges these segments in some order (each used exactly once) with rail pieces connecting consecutive segments. Each rail piece has a nonnegative integer length in meters. Every meter of rail reduces the ride's speed by \(1\) km/h.

The coaster starts with a speed of \(1\) km/h when entering the first segment. The design must satisfy that:

• The speed when entering any segment is at most its \(s_i\).
• The speed is always positive (greater than 0).

Your task is to determine the minimum possible total length of the connecting rails. In the special case where \(m = 0\), you only need to check whether there exists a valid design with all connecting rail lengths equal to zero. If a valid design exists, output 0; otherwise, output -1.

Note: If no valid arrangement exists for the given conditions, output -1.

Explanation of the Sample:

Input:
4 1
1 7
4 3
5 8
6 6
There are 4 segments. The best order is 0, 3, 1, 2 with rail lengths 1, 2, and 0 respectively.
The coaster's journey is as follows:

Start with speed 1 km/h and enter segment 0 (with limit 1 km/h).
Leave segment 0 with speed 7 km/h.
Travel 1 meter of rail, reducing speed to 6 km/h.
Enter segment 3 (limit 6 km/h) with speed 6 km/h and leave it with 6 km/h.
Travel 2 meters of rail, reducing speed to 4 km/h.
Enter segment 1 (limit 4 km/h) with speed 4 km/h and leave it with 3 km/h.
Immediately enter segment 2 (limit 5 km/h) with speed 3 km/h and leave with 8 km/h.

The total rail length is 1+2+0 = 3, which is the minimum possible.

inputFormat

The first line contains two integers \(n\) and \(m\), where \(n\) is the number of segments and \(m\) is a flag. If \(m \neq 0\), your task is to compute the minimum total rail length needed. If \(m = 0\), you only need to determine whether a valid arrangement exists with all connecting rail lengths zero.

The following \(n\) lines each contain two integers \(s_i\) and \(t_i\), representing the speed limit upon entering segment \(i\) and the fixed speed after leaving segment \(i\), respectively.

outputFormat

If a valid design exists, output the minimum possible total rail length (or 0 if \(m = 0\) and a valid design with zero rail lengths exists). Otherwise, output -1.

sample

4 1
1 7
4 3
5 8
6 6

3