Mr. Dorsey Dawson recently stole grams of gold from ACME Jewellers. He is now on a train back home. To avoid getting caught by the police, he has to convert all the gold he has into paper money. He turns into a salesman and starts selling the gold in the train.
There are passengers who have shown interest in buying the gold. The passenger agrees to buy grams of gold by paying dollars. Dawson wants to escape from the police and also maximize the profit. Can you help him maximize the profit?
Note: The passenger would buy exactly grams if the transaction is successful.
The first line contains two space separated integers, and , where is the number of passengers who agreed to buy and is the stolen amount of gold (in grams).
lines follow. Each line contains two space separated integers - and , where is the the value which the passenger has agreed to pay in exchange for grams of gold.
all 's and 's are less than or equal to and greater than .
If it's possible for Dorsey to escape, print the maximum profit he can enjoy, otherwise print Got caught!.
Sample Input 0
4 10460 4590 6550 5590 5
Sample Output 0
Selling it to passengers buying 4 grams and 6 grams would lead to 1050 dollars whereas selling it to passengers buying 5 grams gold would lead to 1140 dollars. Hence the answer.