1226: Булочки -> Баталії Проскурова


Submit solution


Points:5
Time limit:0.1s
Memory limit:64M
Author:

Problem type

Як вже відомо, Вася на канікулах підробляє у кафе, і йому подобається готувати. Якось вирішив він спекти кілька булочок з начинкою та продати їх у кафе. У Васі є 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 цілих числа ai, bi, ci и di (1 ≤ ai, bi, ci, di ≤ 100).

Формат вихідних даних

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

Приклад вхідних даних

10 2 2 1
7 3 2 100
12 3 1 10

Приклад вихідних даних

241

Comments

There are no comments at the moment.