Як вже відомо, Вася на канікулах підробляє у кафе, і йому подобається готувати. Якось вирішив він спекти кілька булочок з начинкою та продати їх у кафе. У Васі є ~n~ грам тіста, та ~m~ різних видів начинки. Види начинки пронумеровані натуральними числами від 1 до ~m~. Вася знає, що ~i~-го виду начинки у нього залишилося ~a_i~ грам. Щоб спекти одну булочку з ~i~-ой начинкою, потрібно рівно ~b_i~ грам цієї начинки і ~c_i~ грам тіста, а продати одну таку булочку можна за ~d_i~ гривен. Крім того, він може спекти булочки без начинки. На кожну таку булочку потрібно ~c_0~ грам тіста, а продати таку булочку можна за ~d_0~ гривен. Вася може спекти будь-яку кількість булочок з різними начинками або без начинки, якщо для цього вистачить тіста і начинки. Всі надлишки, які залишилися після випічки, Вася викидає. Визначте яку максимальну кількість гривень Вася може заробити.

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

У першому рядку містяться 4 цілих числа ~n, m, c_0, d_0~ ~(1 \le n \le 1000~, ~1 \le m \le 10, 1 \le c_0, d_0 \le 100)~. В кожному з наступних ~m~ рядків містяться по 4 цілих числа ~a_i, b_i, c_i, d_i~ ~(1 \le a_i, b_i, c_i, d_i \le 100)~.

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

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

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

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

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

241