#### Registered Users Only

Please login to view and utilize this feature.

## Problem Description

Rar is at a new shopping mall, going shopping. Being the cheapskate he is, he has obtained a total of *C* coupons beforehand, to get cheaper stuff.

He sees a total of *N* items being sold, each with a normal price *P _{i}*, and a discounted price

*D*, which requires the use of

_{i}*R*coupons.

_{i}Given the fact that Rar cannot buy the same item twice, and has a total of *M* dollars, what is the maximum number of items he can buy?

## Input

The first line of input will contain three integers, *N*, *M* and *C*.

The next *N* lines of input will contain three integers each, *P _{i}*,

*D*and

_{i}*R*.

_{i}## Output

The output should contain one integer, the maximum number of items Rar can buy.

## Limits

0 ≤ R_{i} ≤ C, 0 ≤ D_{i} ≤ P_{i} ≤ M.

Subtask 1 (19%): 1 ≤ N ≤ 12, 0 ≤ C ≤ 1000, 0 ≤ M ≤ 10^{9}.

Subtask 2 (10%): 1 ≤ N ≤ 50, 0 ≤ M, C ≤ 50.

Subtask 3 (25%): 1 ≤ N ≤ 100, 0 ≤ M, C ≤ 100.

Subtask 4 (8%): 1 ≤ N ≤ 100, C = 0, 0 ≤ M ≤ 10^{9}.

Subtask 5 (12%): 1 ≤ N ≤ 100, C = 1, 0 ≤ M ≤ 10^{9}.

Subtask 6 (20%): 1 ≤ N ≤ 100, 0 ≤ C ≤ 500, 0 ≤ M ≤ 10^{9}.

Subtask 7 (6%): 1 ≤ N ≤ 500, 0 ≤ C ≤ 1000, 0 ≤ M ≤ 10^{9}.

Subtask 8 (0%): Sample Testcases

## Sample Testcase 1

### Input

4 30 1 10 2 1 9 8 1 20 18 1 5 1 1

### Output

3

## Sample Testcase 2

### Input

5 30 3 25 10 1 35 33 2 4 1 1 15 3 2 10 1 3

### Output

4

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 19 | 22 | 1s | 256MB | Minimum |

2 | 10 | 22 | 1s | 256MB | Minimum |

3 | 25 | 42 | 1s | 256MB | Minimum |

4 | 8 | 20 | 1s | 256MB | Minimum |

5 | 12 | 21 | 1s | 256MB | Minimum |

6 | 20 | 102 | 1s | 256MB | Minimum |

7 | 6 | 142 | 1s | 256MB | Minimum |

8 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o cheapskate -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512