题目描述

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.

输入格式

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$ ).

输出格式

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

题面翻译

面包师 Lavrenty 打算用馅料做几个面包，然后把它们卖掉。

Lavrenty 有 $n$ 克面团和 $m$ 种不同的馅料。馅料种类的下标从 $1$ 到 $m$，他知道他的第 $i$ 种馅料剩下 $a_i$ 克，做一个第 $i$ 种馅料的面包，恰恰需要 $b_i$ 克的i种馅料和 $c_i$ 克的面团，同时这种面包可以卖 $d_i$ 块Tugrik。

他也可以做没有馅的面包。每个这样的面包需要 $c_0$ 克面团，可以卖 $d_0$ 块 Tugrik。所以 Lavrenty 可以做任何数量的包子，用不同的馅料或者不用馅料，除非用完了面团和馅料。Lavrenty 会扔掉烘培面包后剩下的所有多余材料。

求出 Lavrenty 可以赚取的 Tugrik 的最大数量。

样例 #1

样例输入 #1

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

样例输出 #1

241

样例 #2

样例输入 #2

100 1 25 50
15 5 20 10

样例输出 #2

200

提示

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.

@小粉兔