Souvenirs

Time limit1sMemory limit256 MB

Summary

Buy souvenirs from merchants in order with gold and silver coins and choose how to pay each price to maximize the number bought.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Simulation
Solved: No attempts yet

Problem

Buy souvenirs from merchants in order using gold coins (worth $g$ silver) and silver coins. Merchants round change in silver packages as greedy, honest, or generous. Generous merchants require exact silver payment when possible; otherwise pay one gold coin. Other merchants accept exact silver or one gold coin. Maximize purchases.

Input

$g$ , $c$ , $n$ , then $n$ lines with merchant type, package size $p_i$ , and price $s_i$ .

Output

Maximum number of souvenirs you can buy.

Examples4

Example 1
Input
```
42 1 2
generous 21 41
honest 6 21
```
Expected output
```
2
```
Example 2
Input
```
42 1 2
honest 21 11
generous 6 23
```
Expected output
```
1
```

Example 3

Input

12 2 6
greedy 1 5
greedy 1 6
generous 4 7
greedy 4 6
greedy 6 6
honest 2 2

Expected output

Example 4
Input
```
10 1 1
greedy 2 3
```
Expected output
```
1
```