图图 是一名面包师，他准备制作几个带馅的小圆面包并出售。
图图有 n 克面团以及 m 种不同的馅料类型。 将它们从 1 到 m 编号。 他现在知道他第 i 个馅料还剩下ai克。 用第 i 个馅料烹制一个面包需要正好 bi 克的馅料 i 和 ci 克的面团。 这样的小圆面包可以卖di的钱。
他也可以做没有馅的包子。 每个这样的面包需要 c0 克面团，可以卖 d0 的钱。 因此，图图可以任意搭配着使用他所拥有的材料。 图图最多可以赚多少钱。
第一行包含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)。
输出一个数字表示能挣到的最多的钱
10 2 2 1
7 3 2 100
12 3 1 10
241
100 1 25 50
15 5 20 10