27070번 - 전설의 고대 광산 탈출

당신은 전설 속의 고대 광산을 탐험하고 있다. 이 광산 곳곳에는 값비싼 희귀 광석이 넘쳐나지만, 광석을 수집하러 들어갔다가 살아 나온 사람은 단 한 명도 없었다고 전해진다.

직접 방문한 전설의 고대 광산에는 하나의 직선 레일이 놓여 있었다. 당신은 이 레일을 따라 이동하기로 했다. 전설에서 들은 대로 광산 안에는 희귀 광석들이 넘쳐났고, 레일 옆 곳곳에는 고대의 광부들이 광석을 담아 둔 수레가 놓여 있었다. 당신은 총 $N$개의 수레에 대한 정보를 수첩에 기록해 두었다. 당신이 기록한 정보는 구체적으로 다음과 같다.

• $i$번째 수레는 입구로부터 거리가 $x_i$인 곳에 위치한다.
• $i$번째 수레에는 광석 주머니가 하나 담겨 있다. 이 주머니의 질량은 $m_i$이고, 주머니에 담긴 광석의 가치는 $c_i$이다.

당신이 광산 입구로부터 거리가 $X$인 위치에 도달했을 때, 광산 안에서 엄청난 굉음이 들리기 시작했다. 당신은 $T$만큼의 시간이 지나면 광산 전체가 무너져 내릴 것이라는 사실을 직감했고, 근처에 있던 빈 수레를 레일에 얹은 다음 그 위에 올라탔다. 당신과 빈 수레의 질량의 합은 $M$이다. 당신은 수레를 타고 $V$의 속도로 입구를 향해 달리기 시작했다.

레일은 평평한 지형 위에 놓여 있으며 마찰이 없기 때문에, 당신이 달리는 동안 당신이 탄 수레의 운동량(질량과 속도의 곱)은 $MV$로 일정하게 유지될 것이다. 이 속도라면 탈출에 성공할 수 있을 거라는 확신에 찬 당신은, 조금 더 욕심을 내서 달리는 도중 만나는 수레에 담긴 광석 주머니 몇 개를 담아 가기로 결심했다. 당신은 손이 빠르기 때문에 순식간에 옆 수레에서 광석 주머니를 가져올 수 있다. 하지만 주머니를 담을 때마다 당신이 탄 수레는 무거워지고, 운동량 보존의 법칙에 의해 당신이 탄 수레는 느려지게 된다. 구체적으로, 당신이 주머니를 담은 이후의 질량을 $M'$, 그 때의 속도를 $V'$라고 하면, $M'V' = MV$가 성립한다.

당신의 최우선 목표는 전설의 고대 광산을 살아 나오는 것이다. 시간 $T$ 이내에 광산 입구에 도달해야 하며, 정확히 $T$만큼의 시간이 걸려도 괜찮다. 또한 당신은 수레에 담은 광석의 총가치도 최대화하고자 한다. 당신이 전설의 고대 광산을 살아 나오는 것이 가능하다면, 가지고 나올 수 있는 광석의 총가치는 최대 얼마일지 계산하시오.

첫 번째 줄에 $X, T, M, V, N$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄만큼 $x_i, m_i, c_i$가 공백으로 구분되어 주어진다.

당신이 전설의 고대 광산을 탈출하는 것이 가능하다면, 당신이 가지고 나올 수 있는 광석의 총가치가 최대 얼마인지 출력한다.

당신이 전설의 고대 광산을 탈출하는 것이 불가능하다면, $-1$을 출력한다.

• $1 \leq X, T, M, V, N \leq 100$
• $1 \leq x_i \leq X$
• $1 \leq m_i, c_i \leq 10\,000$