C. Булочки
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Пекарь Лаврентий собирается испечь несколько булочек с начинкой на продажу.

У Лаврентия есть n грамм теста, а так же m различных видов начинки. Виды начинки пронумерованы натуральными числами от 1 до m. Лаврентий знает, что i-го вида начинки у него осталось ai грамм. Чтобы испечь одну булочку с i-ой начинкой, нужно ровно bi грамм этой начинки и 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
Выходные данные
200
Примечание

Чтобы получить наибольшее количество тугриков в первом примере, нужно испечь 2 булочки с начинкой 1, 4 булочки с начинкой 2 и одну булочку без начинки.

Во втором примере имеет смысл испечь только 4 булочки без начинки.