문제
정올국에는 1부터 N까지 번호가 매겨진 N개의 집이 순서대로 있다.
각 집에는 사람이 1명씩 산다.
i번 집에 사는 사람을 사람 i라고 하자.
최근 신종 바이러스가 등장하여 모든 사람이 바이러스에 감염되었다.
사람들을 치료하기 위해 M개의 치료 계획이 만들어졌다.
i번 치료 계획의 비용은 Ci이다.
i번 치료 계획이 실행되면, 다음의 일이 벌어진다:
- Ti번째 날의 저녁에, Li <= x <= Ri를 만족하는 사람 x가 감염되어있다면, 사람 x를 치료한다.
바이러스는 다음과 같은 방법으로 퍼진다:
어떤 날의 아침에 사람 x가 감염되어 있었다면, 사람 x-1(x>=2인 경우)와 사람 x+1(x<N인 경우)가 정오에 감염된다.
이미 치료된 적이 있는 사람이 또다시 바이러스에 감염될 수 있다.
정올국의 왕인 준혁이는 몇 개의 치료 계획을 골라, 치료 계획이 모두 끝난 후에는 모든 사람이 바이러스에 감염되어 있지 않도록 하고 싶다.
여러분은 준혁이를 도와 조건을 만족하게 치료 계획을 실행할 수 있는지, 가능하다면 최소 비용은 얼마인지 구하여라
입력
첫 번째 줄에 N과 M이 공백으로 구분되어 주어진다.
두 번째 줄부터 M개의 줄에 걸쳐, i번째 줄에 Ti, Li, Ri, Ci가 공백으로 구분되어 주어진다.
1 <= N <= 1,000,000,000
1 <= M <= 1,000,000
1 <= Ti <= 1,000,000,000
1 <= Li <= Ri <= N
1 <= Ci <= 1,000,000,000
4점짜리 부분문제에 대하여 Ti = 1이다.
5점짜리 부분문제에 대하여 M <= 16이다.
31점짜리 부분문제에 대하여 M <= 5000이다.
출력
첫 번째 줄에 가능하다면 최소 비용을, 불가능하다면 -1을 출력하여라.
예제 #1
10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1
7
예제 #2
10 5
2 6 10 3
1 1 5 5
5 2 7 3
8 6 10 4
4 1 3 1
-1
로그인해야 코드를 작성할 수 있어요.