Description

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 \leq i \leq N$), it will pass through $(j, i)$ ($2 \leq j \leq 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 \leq i \leq 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 \leq C_i \leq 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 \leq i \leq 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.

:::align{center}

Figure: An example of the board of Pinball. $M = 2$, $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 Format

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 \leq i \leq 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 Format

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$.

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

25

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

-1

Hint

Sample 1 Explanation

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.

:::align{center} :::

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

:::align{center} :::

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 2 Explanation

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.

Constraints

All input data satisfy the following conditions.

• $1 \leq M \leq 100\,000$.
• $2 \leq N \leq 1\,000\,000\,000$.
• $1 \leq A_i \leq C_i \leq B_i \leq N$ ($1 \leq i \leq M$).
• $1 \leq D_i \leq 1\,000\,000\,000$ ($1 \leq i \leq M$).

Subtask

Subtask 1 [11 points]

The following conditions are satisfied.

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

Subtask 2 [18 points]

The following condition is satisfied.

• $M \leq 200$.

Subtask 3 [22 points]

The following condition is satisfied.

• $M \leq 1000$.

Subtask 4 [49 points]

There are no additional constraints.