퀘스트

ICPC 월드 파이널스를 앞두고 긴장을 풀기 위해 Quests라는 컴퓨터 게임을 하기로 했다. 이미 여러 번 해 봤으니, 이번에는 완벽한 플레이를 달성하려고 한다. 월드 파이널스에서도 완벽한 플레이를 하기 위한 준비인 셈이다.

이 게임에서는 여러 퀘스트를 완료해야 하고, 각 퀘스트를 완료하면 경험치(XP)를 얻는다. 지금까지 얻은 총 경험치가 현재 레벨을 결정한다. 경험치를 v만큼 얻을 때마다 레벨이 하나 오른다. 정확히 말하면, 어떤 시점의 레벨은 경험치가 L · v 이상인 가장 큰 정수 L이다.

각 퀘스트에는 경험치 x와 목표 난이도 d가 정해져 있다. 레벨이 d 이상일 때 퀘스트를 완료하면 x만큼의 경험치를 얻는다. 반면 레벨이 d보다 낮을 때 퀘스트를 완료하면 c · x만큼의 경험치를 얻는다. 상수 c는 권장 레벨 d보다 낮은 레벨에서 퀘스트를 완료했을 때 보너스를 주는 경험치 배율이다.

n개의 퀘스트와 각각의 x, d 값을 모두 외우고 있다(상수 v와 c도 알고 있다. 이 게임을 아주 많이 해 봤으니까). 또한 목표 난이도와 자신의 레벨에 상관없이 어떤 퀘스트든 완료할 만큼 실력이 좋다. 얻을 수 있는 경험치의 총합이 최대가 되도록 모든 퀘스트를 완료하는 순서를 정하려고 한다.

예를 들어 아래 예제 입력에서 얻을 수 있는 최대 경험치는 43이며, 다음과 같이 하면 된다. 먼저 두 번째 퀘스트를 완료한다(레벨 0이고 목표 난이도 2인 퀘스트를 완료했으므로 4의 경험치를 얻는다). 그다음 첫 번째 퀘스트를 완료한다(아직 레벨 0이고 목표 난이도가 1이므로 30의 경험치를 얻는다). 경험치가 34가 되어 레벨 3이 된다. 마지막으로 세 번째 퀘스트를 완료한다(이미 레벨 3이므로 배율 없이 9의 경험치를 얻는다).

첫 번째 줄에는 세 정수 n, v, c가 주어진다. n (1 ≤ n ≤ 2 000)은 게임에 있는 퀘스트의 수, v (1 ≤ v ≤ 2 000)는 레벨을 하나 올리는 데 필요한 경험치, c (2 ≤ c ≤ 2 000)는 목표 난이도에 도달하기 전에 퀘스트를 완료했을 때 적용되는 경험치 배율이다.

이어서 n개의 줄이 주어지고, 각 줄에는 퀘스트 하나를 나타내는 두 정수 x와 d가 있다. x (1 ≤ x ≤ 2 000)는 목표 난이도 이상일 때 그 퀘스트를 완료해서 얻는 경험치이고, d (1 ≤ di ≤ 106)는 그 퀘스트의 목표 난이도이다.

모든 퀘스트를 완료해서 얻을 수 있는 경험치의 최댓값을 출력한다.