Informatica Online Judge

  리듬게임I [0797 / 031D]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 19   Total Tried : 29


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

GSHS의 일부 학생들이 한다는 리듬 게임은 나오는 노래에 맞춰서 노트를 쳐 그 배점만큼의 점수를 얻는 방식의 게임이다.

모든 노트를 모두 칠 수 있다면 최고 점수를 받을 수 있겠지만, 짧은 간격으로 많은 노트가 나오는 폭타 구간에서는 칠 수 없는 노트가 존재하므로 최고 점수는 거의 불가능하다.

입력에서 게이머의 연타 최소 간격 d가 주어지는데, 이는 치는 두 노트 사이에 적어도 d만큼의 간격이 있어야 한다는 뜻이다.

예를 들어 d가 6이면 1과 7때 나오는 노트는 모두 정확히 칠 수 있지만, 3과 8때 나오는 노트는 둘 중 하나만 정확히 칠 수 있다.


모든 노트를 제 때 치기는 힘들기에, 점수의 판정에는 3가지가 있다.

노트를 제 시간에 정확히 누르는 경우를 PERFECT라고 한다. 이 때 그 노트의 배점을 온전히 받을 수 있다.
시간의 오차가 1일 경우를 GREAT, 2일 경우를 GOOD이라고 하며 각각 배점의 1/2, 1/4를 받는다. (단, 나눗셈의 결과는 정수로 내림한다.)

다시 위의 예를 생각하면, 1과 7때 나오는 노트는 모두 PERFECT로 칠 수 있고, 3과 8때 나오는 노트는 하나는 PERFECT, 나머지 하나는 GREAT으로 칠 수 있다. 한 때에 여러 개의 노트를 칠 수도 있다.

만약 노트가 3, 8, 9때 나온다면 3과 9때 쳐서 각각 PERFECT / GREAT, PERFECT를 받을 수 있다는 것이다.

위의 조건들을 고려해서 게이머가 최대로 낼 수 있는 점수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에는 노래의 길이 l과 노트의 수 n, 그리고 연타 최소 간격 g가 주어진다. (1≤n≤l≤300000, 5≤g≤50)

두 번째 줄부터 n+1번째 줄까지는 노트가 나오는 시간 t와 배점 s가 주어진다. (1≤t≤l, 1≤s≤3000)

Output

첫 번째 줄에 주어진 조건을 만족하면서 최대로 낼 수 있는 점수를 출력하시오.

IO Example

입력
18 10 5
11 227
13 122
17 44
7 121
5 246
8 14
1 188
4 102
14 203
18 14

출력
731

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]