The Dragon Hunt

The Commander of the army in the Kingdom of Hara is on a new quest to capture dragons.

There are \(k\) different breeds of dragon in the kingdom, numbered from \(1\) to \(k\).

To capture a dragon from specific breed, a special type of arrow is needed. The Commander knows that he has \(x_i\) arrows left for the ith dragon type. It takes exactly \(y_i\) arrows and \(s_i\) soldiers to capture a dragon from the \(i^{th}\) dragon breed. Capturing a dragon from \(i^{th}\) breed has a reward of \(g_i\) gold coins.

Also, the “Hungarian Horntail” dragon breed does not require any arrows and can be captured by \(s_0\) number of soldiers and has a reward of \(g_0\) gold coins.

The Commander has an \(n\) number of soldiers in his army. There is an unlimited number of dragons from each breed.

What is the maximum number of gold coins that the Commander can earn?

Input Format

The first line contains 4 integers \(n\), \(k\), \(s_0\),\(g_0\)

Each of the following \(k\) lines contains 4 integers. The \(i^{th}\) line contains numbers \(x_i\), \(y_i\), \(s_i\) and \(g_i\).

Output Format

A single integer - The maximum gold conins the commander can get rewarded.

Constraints

• $1 ≤ n ≤ 10000 $
• \[1  ≤  k  ≤ 100\]
• \[1 ≤ s_0 ,g_0, x_i, y_i, s_i, g_i ≤ 1000\]

Sample Input 0

20 3 2 1
5 4 2 100
12 3 1 10
6 2 5 30

Sample Output 0

220