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 ith line consisting of HPi, MPi, Ci and Ai, representative of the attributes that describe potion 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 ≤ Ai ≤ 10000
0 ≤ HPi, MPi ≤ 30000
M % 100 = 0
Ci % 100 = 0
Subtasks
- Subtask 1 (10%): T≤1
- Subtask 2 (10%): T≤2
- Subtask 3 (20%): Ai = 1
- Subtask 4 (30%): Ai≤10
- 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