돈 걸기

프로그램 명: koi4u_bet

제한시간: 1 초

디자이너 ‘예처르킴’은 최근 세계적인 디자인 시장에서 매번 대박을 터뜨려 요즘 돈이 남아돈다.

‘예처르킴’은 평소에 관심 있던 경마에서 재미를 얻으려 하고 있다. 경마장에는 N마리의 말과 그들이 겨루는 M개의 경기가 있다. ‘예처르킴’은 경마에서 ‘돈 버는 재미’를 보고 싶어해, 경마장에 있는 N마리의 말에 대한 정보를 불법적으로 입수했다.

말에 대한 정보는 다음과 같다.

i번 말은 Si번 경기부터 Ei번 경기까지 연속적이게 뛰고 매번 완주시간이 Ti로 일정하다. i번 말이 우승을 했을 때 i번 말에 돈을 건 사람이 버는 돈은 Ci 이다.

‘예처르킴’은 매 경기마다 어떤 말에게 돈을 걸지 정할 수 있다. ‘예처르킴’은 한 경기에 오직 한 마리의 말에게만 돈을 걸 수 있다. 만약 완주시간이 같아 여러 말이 1등을 했을 때에 최종적으로 우승하는 말은 가장 빨리 도착한 말 중 번호가 제일 작은 말이다.

당신은 ‘예처르킴’을 도와 그가 벌 수 있는 최대 금액을 구해야 한다.

첫 줄에 경기의 수와 말의 수를 나타내는 두 자연수 M, N이 주어진다. (1 ≤ M, N ≤ 100)
그리고 다음 N줄 동안 i+1번째 줄에 i번 말에 대한 정보를 나타내는 네 자연수 Si, Ei, Ti, Ci가 주어진다. (1 ≤ Si ≤ Ei ≤ M, 1 ≤ Ti, Ci ≤ 1,000)

‘예처르킴’이 벌 수 있는 최대 금액을 출력한다.

1, 2번째 경기에서는 1번 말에게 돈을 걸고, 3번째 경기에서는 3번 말에게, 4번째 경기에는 4번 말에게 돈을 걸면 총 60원을 벌 수 있다.

출처:koi4u 2011 모의고사 1 번