小明去新东方学成归来，开了一个包子店。

小明今天打算用不同的馅料做几个包子，然后把它们卖掉。

小明有 n 克面团和 m 种不同的馅料。馅料种类的下标从 1 到 m，他知道他的第 i 种馅料剩下 a_i 克，做一个第 i 种馅料口味的包子，恰恰需要 b_i 克的i种馅料和 c_i 克的面团，同时这种馅料可以卖 d_i 块RMB。

他也可以做没有馅的馒头。每个这样的馒头需要 c_0 克面团，可以卖 d_0 块RMB。所以小明可以做任何数量的包子，用不同的馅料或者不用馅料，除非用完了面团和馅料。作为良心商家，小明会扔掉蒸包子后剩下的所有多余材料。

求出小明可以赚取的RMB的最大数量。

第一行包含4个整数n,m,c_0 , d_0, (1\leq n \leq 100,1 \leq m \leq 10,1 \leq c_0,d_0 \leq 100)

接下来m行包含4个整数。分别是a_i,b_i,c_i,d_i,(1\leq a_i,b_i,c_i,d_i \leq 100)

一个数字，表示小明这一天的最大收益！