14736번 - Coke Challenge

문제

태영이는 콜라를 지나치게 좋아한다. 그래서 단 하루라도 콜라를 마시지 않으면 그는 살 수가 없다. 특히 그는 재민이의 회사에서 제조하는 콜라를 가장 좋아한다. 그러자 재민이는 고마운 마음으로 태영이에게 스폰서를 해주겠다고 했다. 그 말을 들은 태영이는 재민이 회사에서 지원받은 돈으로 대전 최초로 콜라 마시기 대회를 열려고 한다.

콜라 마시기 대회에는 $N$명의 사람이 참가한다. 각 참가자에게 콜라 $K$ mL(밀리리터)가 주어지고, 종이 울리는 순간 콜라를 마시기 시작해서 가장 빨리 모두 마시는 사람이 우승하게 된다. 그런데 콜라를 한 번에 다 마시면 탄산 때문에 매우 고통스럽기 때문에, 각 사람은 마시다가 쉬다가 다시 마시는 것을 반복하며 콜라를 마신다. 구체적으로, 각 참가자가 1초에 마실 수 있는 콜라의 양은 $A$ mL로 동일하고, i번째 참가자는 $t_i$초 동안 콜라를 마시고 $s_i$초 동안 쉬기를 반복한다. 어떤 참가자에게 남은 콜라가 0 mL가 되는 순간 우승자가 결정되며 대회는 끝난다.

$N$명의 참가자의 정보가 주어졌을 때, 우승자가 결정되는 시간은 대회를 시작하고 몇 초 뒤인지 출력하는 프로그램을 작성하라.

입력

첫 번째 줄에 자연수 $N$ (2ドル\leq N\leq 1,000$), $K$ (1ドル\leq K\leq10,000$), $A$ (1ドル\leq A\leq100$)이 주어진다. $K$는 $A$의 배수이다. 다음 $N$개의 줄 중 $i$번째 줄에는 $i$번 참가자의 정보를 나타내는 자연수 $t_i$ (1ドル\leq t_i\leq100$), $s_i$ (1ドル\leq s_i\leq100$)가 주어진다.

출력

첫 번째 줄에 문제의 정답을 출력한다.

제한

힌트