### 问题描述 鲁邦是一位非常出名的甜品师，他有一个小型的甜品店，吸引了大量的顾客。他每天都会制作各种各样的甜品来卖，其中包括有馅料的和无馅料的。 鲁邦现在有 $n$ 克的面团，以及 $m$ 种不同类型的馅料。馅料的编号从 $1$ 到 $m$，他知道他在手上还有 $a_i$ 克的第 $i$ 种馅料。做一个含有第 $i$ 种馅料的甜品需要 $b_i$ 克的馅料和 $c_i$ 克的面团，这种甜品可以卖 $d_i$ 个金币。 鲁邦也可以做无馅料的甜品。每个无馅料的甜品需要 $c_0$ 克的面团，可以卖 $d_0$ 个金币。只要不耗尽面团和馅料，鲁邦可以制作任意数量的含馅料或者无馅料的甜品。制作甜品之后，所有剩余的材料鲁邦都会扔掉。 请你帮助鲁邦计算出他最多可以赚多少金币。 ### 输入格式 第一行包含 $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$)。 ### 输出格式 输出一个整数 — 鲁邦可以赚取的最多金币。 ### 样例输入 ```text 46 5 31 66 24 56 93 19 94 85 26 64 8 34 19 83 43 96 84 24 40 75 41 33 ``` ### 样例输出 ```text 66 ```