- Practice
- Algorithms
- Dynamic Programming
- Dorsey Thief

# Dorsey Thief

# Dorsey Thief

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.

**Input Format**

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.

**Constraints**

- all 's and 's are less than or equal to and greater than .

**Output Format**

If it's possible for Dorsey to escape, print the maximum profit he can enjoy, otherwise print `Got caught!`

.

**Sample Input 0**

```
4 10
460 4
590 6
550 5
590 5
```

**Sample Output 0**

```
1140
```

**Explanation 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.

**Sample Input 1**

```
4 9
100 5
120 10
300 2
500 3
```

**Sample Output 1**

```
Got caught!
```

**Explanation 1**

There is no way to sell all 9 grams of gold.