题目描述

面包师 Lavrenty 打算做几批带馅的面包卖钱。

Lavrenty 有 $n$ 克面团和 $m$ 种馅料，馅料编号 1 到 $m$。他知道第 $i$ 种馅料还剩 $a_i$ 克。做一个第 $i$ 种馅料的面包恰好需要 $b_i$ 克该馅料和 $c_i$ 克面团，这样的面包可以卖 $d_i$ 图格里克。

他还可以做不带馅的面包：每个需要 $c_0$ 克面团，可以卖 $d_0$ 图格里克。也就是说，只要面团和馅料没用完，Lavrenty 想做多少带馅或不带馅的面包都行。烤完后剩下的材料全部扔掉。

求 Lavrenty 最多能赚多少图格里克。

输入格式

第一行包含 4 个整数 $n$、$m$、$c_0$、$d_0$（$1 \le n \le 1000$，$1 \le m \le 10$，$1 \le c_0, d_0 \le 100$）。接下来 $m$ 行每行 4 个整数：第 $i$ 行是 $a_i$、$b_i$、$c_i$、$d_i$（$1 \le a_i, b_i, c_i, d_i \le 100$），分别表示第 $i$ 种馅料的剩余克数、每个面包消耗的馅料克数、消耗的面团克数和售价。

输出格式

输出一个数——Lavrenty 能赚到的最大图格里克数。

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

241

100 1 25 50
15 5 20 10

200

说明/提示

第一组样例要赚最多图格里克，需要做 2 个 1 号馅料的面包、4 个 2 号馅料的面包和 1 个不带馅的面包。

第二组样例中 Lavrenty 应该做 4 个不带馅的面包。