Pinball

Sangsu likes the game Pinball. The rules are as follows.

The pinball board is a grid of square cells with $M+2$ rows and $N$ columns. Row 1 is the top of the board and row $M+2$ is the bottom. The cell in row $i$ and column $j$ is written $(i, j)$.

A ball appears on one of the cells in row 1 and falls straight down toward the bottom. A ball that appears at $(1, i)$ ($1 \le i \le N$) passes through $(j, i)$ ($2 \le j \le M+1$) and lands on the bottom cell $(M+2, i)$. Sangsu scores a point when he hits the ball back.

Hitting the ball back is hard because the ball can land on any cell of the bottom row. Sangsu wants to install the devices described below on the board so that exactly one bottom cell is reachable.

There are $M$ devices, numbered 1 to $M$, and each device is parallel to the rows of the board. Device $i$ ($1 \le i \le M$) sits on the cells from $(i+1, A_i)$ to $(i+1, B_i)$, so it covers $B_i - A_i + 1$ cells. When a ball reaches a cell covered by this device, the ball is carried to $(i+1, C_i)$. The ball then falls straight down along column $C_i$. A single device never interacts with the same ball more than once.

Installing device $i$ costs $D_i$ won. Sangsu picks some of the $M$ devices and installs them so that exactly one bottom cell is reachable, and he wants the total cost to be as small as possible.

The figure above shows a board with $M = 2$ and $N = 4$. A ball appears at the top cell $(1, 2)$. It moves down to $(2, 2)$, device $1$ carries it to $(2, 3)$, and it finally lands on the bottom cell $(4, 3)$.

Given the size of the board and the information about the devices, write a program that computes the minimum cost of installing devices so that exactly one bottom cell is reachable.

Read the following data from standard input.

The first line contains two integers $M$ and $N$ separated by a space. The board has $M+2$ rows and $N$ columns, and there are $M$ devices.

Each of the next $M$ lines contains four integers $A_i$, $B_i$, $C_i$, $D_i$ separated by spaces, where line $i$ ($1 \le i \le M$) describes device $i$. Device $i$ sits on the $B_i - A_i + 1$ cells from $(i+1, A_i)$ to $(i+1, B_i)$, and it carries a ball that reaches any cell it covers to $(i+1, C_i)$. Installing it costs $D_i$ won.

Print on the first line the minimum cost of installing devices so that exactly one bottom cell is reachable. If no such installation exists, print $-1$.

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

The board and the device positions of the first example are shown below. The number written on each device is its installation cost.

Installing devices $2$, $4$ and $5$ out of the five gives the board below.

Now, whichever top cell the ball appears on, it lands on the bottom cell $(7, 3)$. The three devices cost $25$ won in total. No installation cheaper than $25$ won leaves exactly one reachable bottom cell, so the answer is $25$.