Олимпиадный тренинг

Задача . C. Булочки

Задача

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

У Лаврентия есть n грамм теста, а так же m различных видов начинки. Виды начинки пронумерованы натуральными числами от 1 до m. Лаврентий знает, что i-го вида начинки у него осталось a_i грамм. Чтобы испечь одну булочку с i-ой начинкой, нужно ровно b_i грамм этой начинки и c_i грамм теста, а продать одну такую булочку можно за d_i тугриков.

Кроме того, он может испечь булочки без начинки. На каждую такую булочку нужно c₀ грамм теста, а продать такую булочку можно за d₀ тугриков. Лаврентий может испечь любое количество булочек с различными начинками или без начинки, если для этого хватит теста и начинки. Все излишки, которые остались после выпечки, Лаврентий выкидывает.

Определите какое максимальное количество тугриков Лаврентий может заработать.

Входные данные

В первой строке содержатся 4 целых числа n, m, c₀ и d₀ (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10, 1 ≤ c₀, d₀ ≤ 100). В каждой из последующих m строк содержится по 4 целых числа. В i-ой из них находятся числа a_i, b_i, c_i и d_i (1 ≤ a_i, b_i, c_i, d_i ≤ 100).

Выходные данные

Выведите единственное число — максимальное количество тугриков, которые Лаврентий может заработать.

Примечание

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

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

Примеры

№	Входные данные	Выходные данные
1	10 2 2 1 7 3 2 100 12 3 1 10	241
2	100 1 25 50 15 5 20 10	200

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет