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