C. Шанзтай боов

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нарийн боовчин Лаврентыйд $n$ грамм гурил $m$ төрлийн шанз байгаа. Шанзнууд $1$-ээс $m$ хүртэл дугаарлагдсан. Түүнд нийт $i$-р төрлийн шанзнаас $a_i$ грамм үлдсэн байгаа ба ийм шанзтай боов хийхэд $b_i$ грамм шанз, $c_i$ грамм гурил хэрэгтэй болох ба тус бүр нь $d_i$ төгрөгөөр зарагдана.

Бас тэр шанзгүй боов хийж чадна. Шанзгүй боов хийхэд $c_0$ грамм гурил хэрэглэгдэж, $d_0$ төгрөгөөр зарагдана.

Лаврентый материал хүрж л байвал шанзтай шанзгүй бүх төрлийн боовыг хийж чадна. Тийм бол өгөгдсөн материалуудаа ашиглан Лаврентый хамгийн ихдээ хэдэн төгрөгний үнэ бүхий боовнууд хийж чадах вэ. (Зарим төрлийн материал хэрэглэгдэлгүй илүү гарж болно)

Оролт

Эхний мөрөнд $4$ бүхэл тоо $n$, $m$, $c_0$, $d_0$ ($1 ≤ n ≤ 1000$; $1 ≤ m ≤ 10$; $1 ≤ c_0, d_0 ≤ 100$).

Дараагийн $m$ мөрөнд мөр бүрд $a_i$, $b_i$, $c_i$, $d_i$ ($1 ≤ a_i, b_i, c_i, d_i ≤ 100$) тоонууд байна.

Гаралт

Лаврентыйгийн олж чадах хамгийн их мөнгөний хэмжээ.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
10 2 2 1
7 3 2 100
12 3 1 10
Гаралт
241
Оролт
100 1 25 50
15 5 20 10
Гаралт
200

Тэмдэглэл

To get the maximum number of tugriks in the first sample, you need to cook 2 buns with stuffing 1, 4 buns with stuffing 2 and a bun without any stuffing.

In the second sample Lavrenty should cook 4 buns without stuffings.

Сэтгэгдлүүдийг ачааллаж байна...