Problems
철기는 바게트 빵을 너무나 좋아한다. 어느 날 철기는 정말 특이한 바게트 빵을 사게 되었다. 일반적인 바게트 빵과 마찬가지로 철기가 새로 산 바게트 빵은 기다란 모양을 띄고 있다. 그러나 이 바게트 빵은 정확히 직사각형의 형태로 되어 있다.
바게트 빵의 맨 위쪽을 0 이라고 하고, 맨 오른쪽을 L 이라고 하자. 여기서 위쪽에서 a만큼 떨어진 위치부터 b (a < b)만큼 떨어진 위치까지의 연속된 구간을 잘라서 먹게 되면 D 만큼의 맛을 느낄 수 있을 것으로 예상한다.
단순히 한 부분을 자르는 게 아니라 여러 부분을 자를 수 있으나, 자르고자 하는 위치가 겹치는 경우(예를 들어 2부터 4까지의 구간을 자르고자 결정하면 3부터 5까지의 구간)는 자를 수 없게 된다. 하지만 2부터 4까지의 구간을 자르려고 결정 했을 경우 4부터 8까지의 구간이 존재할 경우는 4부터 8까지의 구간 역시 자를 수 있다고 간주한다.
철기가 자르고자 하는 N 개의 구간이 주어지고, 각 구간마다 느낄 수 있을 것이라고 예상 되는 맛의 기대치가 주어졌을 때, 구간을 겹치지 않고 잘라진 구간의 맛의 기대치 합이 최대화가 되게끔 바게트를 자르는 프로그램을 작성하라.
Input
입력의 첫 번째 줄은 바게트의 길이 L (1≤L≤10,000)과 철기가 자르고자 하는 구간의 개수 N (N≤1,000)이 주어진다.
그 다음 줄부터 N개의 줄에는 연속된 특정 구간의 시작과 끝을 뜻하는 자연수 a, b(0≤a<b≤L)와 해당 구간을 잘랐을 때 느낄 수 있는 맛의 기대치 D(-100 ≤ D ≤ 100)가 주어진다. 범위가 동일한 즉, 다시 말해서 어떤 구간 a, b와 부분적으로 겹치는 구간은 존재할 수 있으나, 완전히 겹치는 두 개의 구간은 주어지지 않는다. 다시 말해서 구간 3 5가 나왔을 경우 3 5가 다시 나오는 경우는 없다.
Output
입력에 대해 철기가 바게트를 잘랐을 경우 얻을 수 있는 맛의 기대치의 합이 최대화가 될 경우 그 값을 출력한다.
Example
8 3
0 4 8
3 6 10
5 7 3
11
You must sign in to write code.