Gym

https://vjudge.net/problem/Gym-102058M

Mr. Jeong really loves coke. He loves so much that he drinks coke everyday without exception. One day, he decided to open a coke contest in Daejeon. To the winner, a box of cokes will be given!

N people participate in the contest. Each participant is given K mL of coke, and the one who finishes his/her coke earliest wins the contest. But it is painful to drink the whole coke in one time, so each person repeats drinking and taking a rest. More specifically, as soon as the contest starts, the ith participant starts to drink for ti seconds, then takes a rest for si seconds, and repeats this process until no more coke remains. Moreover, everyone drinks A mL per second. The contest is over if one of the participants finished his/her coke.

Given the infomation of N participants, determine after how many seconds the contest is finished, since the contest begins.

Input

The input starts with the first line containing three integers N (2 ≤ N ≤ 1000), K (1 ≤ K ≤ 10000), and A (1 ≤ A ≤ 100). The ith of the next N lines contains two integers ti (1 ≤ ti ≤ 100) and si (1 ≤ si ≤ 100), the information of ith participant. K is a multiple of A.

Output

Write a single integer, the answer to the question.

Examples

Input

2 100 1
10 5
5 10

Output

145

Input

4 100 2
30 30
49 2
50 50
20 10

Output

50

题意分析：

有一个喝汽水比赛，每个人喝 t 秒后必须休息 s 秒， 一共K毫升汽水，每秒可以喝 a 毫升，一旦有一个人喝完汽水，比赛结束，求比赛结束的时间。

解题思路：

对每个人喝完时间进行比较，找出最短的那一个， 如果一个人喝完汽水，那后面的等待时间就不用有。

第一次 sum=(s+t)*(k/t);  后面的 k/t 没加括号错了1次。

#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
	int n, k, a, ans, sum, t, s; 
	while(scanf("%d%d%d", &n ,&k, &a)!=EOF)
	{
		ans=99999999;
		k/=a;
		while(n--)
		{
			scanf("%d%d", &t, &s);
			sum=(s+t)*(k/t);
			if(k%t==0)
				sum-=s;
			else
				sum+=k%t;
			ans=min(ans, sum);
		}
		printf("%d
", ans);
	}
	return 0;
}