#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Admist the current chaos in the Maple World, x3JiaYin the Mercedes is preparing for her epic battle against the Black Mage. However, even though she has *Elven Healing*, which utilizes energy purified by nature to continously recover HP and MP, this amount is insufficent as it only regenerates 5% of x3JiaYin's MaxHP and MaxMP per 4 second.

As such, she decides to bring along some potions in order to replenish her HP and MP in the battle against the Black Mage. Sadly, after paying 10m for the *Unicorn Special Meal* required to feed her dear *Charlie the Unicorn*, x3JiaYin is only left with **M** mesos (the currency that Maple World uses).

Walking along Elluel, she met *Erwin, the Merchant* who specializes in selling potions. *Erwin* has **T** different types of potions in stock of different quantities. Each potion recovers a certain amount of HP and/or MP but some positive amount of mesos are required to purchase it.

Each potion can be described with the following attributes:

- HP Recovered - The amount of HP this potion will recover if it was utilized.
- MP Recovered - The amount of MP this potion will recover if it was utilized.
- Price - The price of purchasing this potion, in mesos.

In order to optimize the amount of HP and MP the potions she buys will recover, she has enlisted for your help. Given the list, description and amount of potions *Erwin* sells, determine the maximum amount of *HP and MP regeneration* x3JiaYin can recover from the potions purchased from *Erwin* using less than **M** mesos in total.

*HP and MP regeneration* is defined as sum of the total number of HP recovered and MP recovered of all the potions.

## Input

The first line of input consists of 2 integers, **M** followed by **T**.

Subsequently, **T** lines of input will each consist of 4 integers each, with the *i _{th}* line consisting of

*HP*,

_{i}*MP*,

_{i}*C*and

_{i}*A*, representative of the attributes that describe potion

_{i}*i*: HP Recovered, MP Recovered, Price for a single potion and quantity of the potion

*Erwin*has in stock.

## Output

A single integer, denoting the maximum *HP and MP regeneration* that can be obtained through the purchase of potions.

## Limits

0 ≤ **T** ≤ 100

0 ≤ **M** ≤ 1000000

0 ≤ *A _{i}* ≤ 10000

0 ≤ *HP _{i}*,

*MP*≤ 30000

_{i}**M** % 100 = 0

** C_{i}** % 100 = 0

## Subtasks

- Subtask 1 (10%):
**T**≤1 - Subtask 2 (10%):
**T**≤2 - Subtask 3 (20%):
*A*= 1_{i} - Subtask 4 (30%):
*A*≤10_{i} - Subtask 5 (30%): Refer to
*Limits*.

## Sample Input 1

10000 1 500 500 1000 7

## Sample Output 1

7000

## Sample Input 2

10000 2 250 500 500 15 500 0 500 10

## Sample Output 2

13750

## Sample Input 3

10000 5 50 0 100 10000 100 100 200 10000 200 100 200 10000 500 400 700 10000 1000 0 900 10000

## Sample Output 3

15000

### Tags

### Subtasks and Limits

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

1 | 10 | 1 | 0.3s | 512MB | Minimum |

2 | 10 | 1 | 0.3s | 512MB | Minimum |

3 | 20 | 2 | 0.3s | 512MB | Minimum |

4 | 30 | 3 | 0.3s | 512MB | Minimum |

5 | 30 | 3 | 0.3s | 512MB | Minimum |

6 | 0 | 3 | 0.3s | 512MB | Minimum |

### Judge Compile Command

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