← 返回题目列表

Codeforces · 106/C

C. 包子

中文机器翻译题面 查看原题

面包师拉夫伦蒂(Lavrenty)打算制作几个带馅的面包并出售。

Lavrenty 有 n 克面团以及 m 种不同的馅料类型。馅料种类从1到m编号。拉夫伦蒂知道他还剩下 ai 克第 i 个馅料。做一个有第 i 个馅料的包子,正好需要 i 克馅料和 ci 克面团。这样的小圆面包可以卖给迪图格里克。

他还可以做没有馅的包子。每个这样的面包需要c0克面团,可以卖d0图格里克。因此,拉夫伦蒂可以用不同的馅料或不加馅料来烹饪任意数量的面包,除非他用完面团和馅料。拉夫连季扔掉烘烤后剩下的所有多余材料。

找出 Lavrenty 可以获得的最大图格里克数量。

输入

第一行包含 4 个整数 n、m、c0 和 d0 (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10, 1 ≤ c0, d0 ≤ 100)。接下来的 m 行每行包含 4 个整数。第 i 行包含数字 ai、bi、ci 和 di (1 ≤ ai、bi、ci、di ≤ 100)。

输出

打印唯一的数字 — Lavrenty 可以获得的最大图格里克数量。

示例

输入 #1

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

输出 #1

241

输入 #2

100 1 25 50
15 5 20 10

输出 #2

200

注意

要在第一个样本中获得最大数量的图格里克,您需要煮 2 个带馅料 1 的面包、4 个带馅料 2 的面包和一个不带任何馅料的面包。

在第二个示例中,Lavrenty 应该煮 4 个不带馅料的面包。