CF106C.Buns

Lavrenty, a baker, is going to make several buns with stuffings and sell them.

Lavrenty has n grams of dough as well as m different stuffing types. The stuffing types are numerated from 1 to m. Lavrenty knows that he has a__i grams left of the i-th stuffing. It takes exactly b__i grams of stuffing i and c__i grams of dough to cook a bun with the i-th stuffing. Such bun can be sold for d__i tugriks.

Also he can make buns without stuffings. Each of such buns requires _c_0 grams of dough and it can be sold for _d_0 tugriks. So Lavrenty can cook any number of buns with different stuffings or without it unless he runs out of dough and the stuffings. Lavrenty throws away all excess material left after baking.

Find the maximum number of tugriks Lavrenty can earn.

拉夫连季是一名面包师，他计划制作若干个带馅料的包子并出售。

拉夫连季拥有 $n$ 克面团，以及 $m$ 种不同的馅料。这些馅料编号为 $1$ 到 $m$。拉夫连季知道第 $i$ 种馅料还剩 $a_i$ 克。制作一个使用第 $i$ 种馅料的包子，恰好需要 $b_i$ 克该种馅料和 $c_i$ 克面团，且该包子可售出 $d_i$ 图格里克（货币单位）。

此外，他还可以制作无馅料的包子。每个无馅料包子需消耗 $c_0$ 克面团，可售出 $d_0$ 图格里克。因此，拉夫连季可以任意制作不同馅料（或无馅料）的包子，只要不超出面团及各馅料的现有库存即可。烘焙完成后，所有剩余材料均被丢弃。

求拉夫连季所能获得的最大图格里克收入。

The first line contains 4 integers n, m, _c_0 and _d_0 (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10, 1 ≤ _c_0, _d_0 ≤ 100). Each of the following m lines contains 4 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).

第一行包含 4 个整数 $n$、$m$、$c_0$ 和 $d_0$（$1 ≤ n ≤ 1000$，$1 ≤ m ≤ 10$，$1 ≤ c_0, d_0 ≤ 100$）。接下来的 $m$ 行每行包含 4 个整数。第 $i$ 行包含数字 $a_i$、$b_i$、$c_i$ 和 $d_i$（$1 ≤ a_i, b_i, c_i, d_i ≤ 100$）。

Print the only number — the maximum number of tugriks Lavrenty can earn.

输出唯一的数字——拉夫连季能够赚取的最多图格里克数。

To get the maximum number of tugriks in the first sample, you need to cook 2 buns with stuffing 1, 4 buns with stuffing 2 and a bun without any stuffing.

In the second sample Lavrenty should cook 4 buns without stuffings.

要在第一个样例中获得最多的图格里克数，你需要制作 2 个含馅料 1 的包子、4 个含馅料 2 的包子，以及 1 个不含馅料的包子。

在第二个样例中，拉夫连季应制作 4 个不含馅料的包子。