Contest Day 2 - JOI Open Contest

Alice likes a video game named Pinball. The rule of Pinball is as follows.

The board of Pinball is a grid of squares with $(M+2)$ rows and $N$ columns. The first row of the board is the top of the board, and the $(M+2{)}^{nd}$ row of the board is the bottom of the board. The square in the $i^{th}$ row and the $j^{th}$ column is denoted by $(i,j)$.

A ball appears at one of the squares on the first row of the board, and it falls down vertically towards the bottom of the board. That is to say, if a ball appears in the square $(1,i)$ $(1\le i\le N)$, it will pass through $(j,i)$ $(2\le j\le M+1)$, and it will arrive at $(M+2,i)$ in the bottom. Alice will get a score when she hits back the ball successfully.

One day, Alice noticed that it is difficult to hit back the ball because a ball can arrive at any squares in the bottom. Alice decided to put some of the following devices on the board appropriately so that there is only one square in the bottom where a ball can possibly arrive.

There are $M$ devices numbered from $1$ to $M$. Each device is parallel to the rows of the board. The device $i$ $(1\le i\le M)$ sits in squares from $(i+1,A_i)$ to $(i+1,B_i)$. Hence it covers $(B_i-A_i+1)$ squares in total. When a ball arrives at some square on this device, the ball will be transferred to the square $(i+1,C_i)$ $(A_i\le C_i\le B_i)$. After that, the transferred ball will move vertically along the column $C_i$. One device will not interact with a ball more than once.

She needs to pay $D_i$ yen in the game to put the device $i$ $(1\le i\le M)$ on the board. She will choose some of the $M$ devices and put them on the board so that there is only one square in the bottom where a ball can possibly arrive. She would like to minimize the total cost by putting devices efficiently.

Figure: An example of the board of Pinball. $M=1$, $N=4$. A ball appears in the square $(1,2)$ in the first row. Then, the ball will move to $(2,2)$, and it will be transferred to $(2,3)$ by the device $1$. It finally arrives at the square $(4,3)$ in the bottom.

Task

Write a program which, given the size of the board and the information of the devices, calculates the minimum of the total cost needed to put devices on the board so that there is only one square in the bottom where a ball can possibly arrive.

Input Specification

Read the following data from the standard input.

• The first line of input contains two space separated integers $M$, $N$. This means the board has $(M+2)$ rows and $N$ columns and the number of devices is $M$.
• The $i^{th}$ line $(1\le i\le M)$ of the following $M$ lines contains four space separated integers $A_i$, $B_i$, $C_i$, $D_i$. This means the device $i$ sits in squares from $(i+1,A_i)$ to $(i+1,B_i)$. The device $i$ covers $(B_i-A_i+1)$ squares in total. The device $i$ will transfer a ball arrived at one of these squares to the square $(i+1,C_i)$. The cost to put the device $i$ is $D_i$ yen.

Output Specification

Write one line to the standard output. The output should contain one integer which denotes the minimum of the total cost needed to put devices on the board so that there is only one square in the bottom where a ball can possibly arrive. If it is not possible to put devices satisfying these conditions, write -1.

Constraints

All input data satisfy the following conditions.

• $1\le M\le 100000$.
• $1\le N\le 1000000000$.
• $1\le A_i\le C_i\le B_i\le N$ $(1\le i\le M)$.
• $1\le D_i\le 1000000000$ $(1\le i\le M)$.

Subtasks

Subtask 1 [11 points]

The following conditions are satisfied:

• $M\le 10$.
• $N\le 1000$.

Subtask 2 [18 points]

The following condition is satisfied:

• $M\le 200$.

Subtask 3 [22 points]

The following condition is satisfied:

• $M\le 1000$.

Subtask 4 [49 points]

No additional constraints.

Sample Input 1

5 6
2 4 3 5
1 2 2 8
3 6 5 2
4 6 4 7
2 4 3 10

Sample Output 1

25

Explanation for Sample 1

The board and the positions of the devices are as in the following figure. The number written above each device denotes the cost needed to put it on the board.

If three devices 2; 4; 5 among five devices are put, the board becomes as in the following figure.

Then, a ball which appears in any square in the first row will arrive at the square $(7,3)$ in the bottom. The total cost to put these devices is 25 yen. You should output 25 because it is impossible to put devices on the board so that the total cost is less than 25 yen and there is only one square in the bottom where a ball can possibly arrive.

Sample Input 2

3 5
2 4 3 10
1 3 1 20
2 5 4 30

Sample Output 2

-1

Explanation for Sample 2

It is impossible to put devices on the board so that there is only one square in the bottom where a ball can possibly arrive.