핀볼

상수는 핀볼 게임을 좋아한다. 핀볼의 규칙은 다음과 같다.

핀볼의 놀이판은 $M+2$행 $N$열의 정사각형 격자판이다. 첫 번째 행은 판의 꼭대기이고, $M+2$번째 행은 바닥이다. $i$번째 행의 $j$번째 열에 있는 칸을 $(i, j)$로 나타낸다.

공은 첫 번째 행의 칸 하나에 나타나서 바닥을 향해 수직으로 떨어진다. 즉 $(1, i)$ ($1 \le i \le N$)에 나타난 공은 $(j, i)$ ($2 \le j \le M+1$)를 차례로 지나 바닥의 $(M+2, i)$에 도착한다. 상수는 공을 되받아 치면 점수를 얻는다.

공이 바닥의 어느 칸에나 도착할 수 있어서 되받아 치기가 어렵다. 그래서 상수는 아래에 설명한 장치를 놀이판에 알맞게 설치해서, 공이 도달할 수 있는 바닥 칸이 하나만 남도록 하려고 한다.

장치는 $1$번부터 $M$번까지 $M$개가 있고, 각 장치는 놀이판의 행과 나란하다. $i$번 ($1 \le i \le M$) 장치는 $(i+1, A_i)$부터 $(i+1, B_i)$까지의 칸에 놓여 있으므로 $B_i - A_i + 1$개의 칸을 덮는다. 공이 이 장치가 덮은 칸에 닿으면 공은 $(i+1, C_i)$로 옮겨진다. 그 뒤 공은 $C_i$번 열을 따라 다시 수직으로 떨어진다. 한 장치가 같은 공과 두 번 이상 상호작용하는 일은 없다.

$i$번 장치를 설치하려면 $D_i$원을 내야 한다. 상수는 $M$개의 장치 중 일부를 골라 설치해서 공이 도달할 수 있는 바닥 칸이 하나만 남게 하고, 그 총비용을 최소로 하려고 한다.

위 그림은 $M = 2$, $N = 4$인 놀이판의 예이다. 공이 꼭대기의 $(1, 2)$에 나타나면 $(2, 2)$로 내려간 뒤 $1$번 장치에 의해 $(2, 3)$으로 옮겨지고, 마침내 바닥의 $(4, 3)$에 도착한다.

놀이판의 크기와 장치 정보가 주어질 때, 공이 도달할 수 있는 바닥 칸이 하나만 남도록 장치를 설치하는 최소 비용을 구하는 프로그램을 작성하시오.

표준 입력으로 다음 데이터를 받는다.

첫째 줄에 두 정수 $M$과 $N$이 공백을 사이에 두고 주어진다. 놀이판은 $M+2$행 $N$열이고, 장치의 수는 $M$개다.

다음 $M$개 줄 중 $i$번째 줄 ($1 \le i \le M$)에는 네 정수 $A_i$, $B_i$, $C_i$, $D_i$가 공백을 사이에 두고 주어진다. $i$번 장치는 $(i+1, A_i)$부터 $(i+1, B_i)$까지 $B_i - A_i + 1$개의 칸에 놓여 있고, 자신이 덮은 칸에 도달한 공을 $(i+1, C_i)$로 옮긴다. 이 장치의 설치 비용은 $D_i$원이다.

첫째 줄에 공이 도달할 수 있는 바닥 칸이 하나만 남도록 장치를 설치하는 최소 비용을 출력한다. 그렇게 설치하는 방법이 없으면 $-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$)

첫 번째 예제의 놀이판과 장치 위치는 아래 그림과 같다. 장치 위에 적힌 수는 그 장치의 설치 비용이다.

다섯 장치 중 $2$번, $4$번, $5$번을 설치하면 놀이판은 아래와 같아진다.

이때 꼭대기의 어느 칸에 공이 나타나도 공은 바닥의 $(7, 3)$에 도착한다. 세 장치의 설치 비용을 더하면 $25$원이다. $25$원보다 적은 비용으로는 공이 도달할 수 있는 바닥 칸을 하나로 만들 수 없으므로 $25$를 출력한다.