1558 - Buns:: HUST Online Judge

1558 - Buns

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 104

Solved: 17

Description

Jianhe25 is a baker. The only food he can cook is buns with creams. Jianhe25 want to sell buns.

Jianbe25 has n grams of dough and m different cream types which number is from 1 to m. Jianhe25 knows that he has a_i grams

left of the i-th cream.

To cook a bun with the i-th cream, Jianhe25 must use exactly b_i grams of cream i and c_i grams of dough. Such bun can be

sold for $ d_i .

He also can make buns without creams which requires c₀ grams of dough. And this creams can be sold for $ d₀. So Jianhe25 can

cook any number of buns with different creams unless he runs out of dough and the creams. Jianhe25 throws away all excess

material left after baking.

Find the maximum money Jianhe25 can earn.

Input

Several test cases. The first line contains four integers n, m, c₀ and d₀ (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10, 1 ≤ c₀, d₀ ≤ 100). Each of the following m lines contains four integers. The i-th line contains numbers a_i, b_i, c_i and d_i (1 ≤ a_i, b_i, c_i, d_i ≤ 100).

Output

For each test case print one line ---- the the maximum number of money Jianhe25 can earn.

sample input

10 2 2 1
7 3 2 100
12 3 1 10

100 1 25 50
15 5 20 10

sample output

241
200

hint

You can use this form of code to deal with several test cases.

while (scanf(...) != EOF)

{

//Your codes here.

}

or

while (cin >> input)
{
//your code here
}

source

The 6th ACM Programming Contest of HUST