CF106C Buns

Lavrenty 是一名面包师，他打算制作若干带馅的面包并出售。 Lavrenty 有 $n$ 克面团，以及 $m$ 种不同类型的馅料。馅料类型编号为 $1$ 到 $m$。Lavrenty 知道他还剩下第 $i$ 种馅料 $a_i$ 克。制作一个第 $i$ 种馅料的面包需要恰好 $b_i$ 克该种馅料和 $c_i$ 克面团。这样的面包可以卖 $d_i$ 图格里克。 他也可以制作没有馅料的面包。每个这样的面包需要 $c_0$ 克面团，可以卖 $d_0$ 图格里克。因此，Lavrenty 可以制作任意数量的带不同馅料或无馅料的面包，直到面团和馅料用完为止。烘焙后剩余的所有材料都会被丢弃。 请你计算 Lavrenty 能获得的最大图格里克数。

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

输出一个整数，表示 Lavrenty 能获得的最大图格里克数。

在第一个样例中，为了获得最大图格里克数，需要制作 2 个 1 号馅料的面包，4 个 2 号馅料的面包，以及 1 个无馅料的面包。 在第二个样例中，Lavrenty 应该制作 4 个无馅料的面包。 由 ChatGPT 4.1 翻译