N керує овочевим складом і відповідає за розробку плану продажу овочів.

На складі зберігаються овочі $n$ видів. N має врахувати властивості різних видів овочів та інші чинники й розробити розумний план продажу, щоб отримати найбільший дохід.

Продаж кожної одиниці овочів виду $i$ приносить дохід $a_i$.

Крім того, оскільки державна політика заохочує продавців урізноманітнювати асортимент, під час першого продажу овочів виду $i$ надається додатковий дохід $s_i$.

На початку роботи запас овочів виду $i$ становить $c_i$ одиниць.

Проте овочі зберігають свіжість обмежений час, і після псування продавати їх не можна. Кмітливий N уже визначив момент псування кожної одиниці: для виду $i$ задано показник $x_i$, і наприкінці кожного дня псуються $x_i$ одиниць, доки не зіпсуються всі овочі. (Зверніть увагу: момент псування кожної одиниці фіксований і не змінюється через продажі.)

Формально, для кожного додатного цілого $d$, для якого $d\times x_i\le c_i$, наприкінці дня $d$ псуються $x_i$ одиниць овочів.

Зокрема, якщо $(d-1)\times x_i\le c_i<d\times x_i$, то наприкінці дня $d$ псуються $c_i-(d-1)\times x_i$ одиниць овочів.

Зауважте, що $x_i=0$ означає, що овочі цього виду не псуються.

Загальна кількість овочів, яку можна продати за день, також обмежена: вона не може перевищувати $m$ одиниць.

N має $k$ запитань і просить вас допомогти з обчисленнями. Кожне запитання має такий вигляд: для заданого $p_j$ який найбільший дохід можна отримати, якщо продавати овочі протягом $p_j$ днів?

Вхідні дані

Дані зчитуються з файлу vegetables.in.

Перший рядок містить три додатні цілі числа $n,m,k$: кількість видів овочів, найбільшу загальну кількість одиниць овочів, яку можна продати за день, і кількість запитань N відповідно.

Кожен із наступних $n$ рядків містить чотири невід'ємні цілі числа $a_i,s_i,c_i,x_i$, що описують один вид овочів і мають наведені вище значення.

Кожен із наступних $k$ рядків містить одне невід'ємне ціле число $p_j$ із наведеним вище значенням.

Вихідні дані

Результати виводяться до файлу vegetables.out.

Виведіть $k$ рядків, кожен з одним цілим числом. Число в рядку $i$ має бути відповіддю на запитання $i$.

Приклади

Вхідні дані 1

2 3 2
3 3 3 3
2 5 8 3
1
3

Вихідні дані 1

16
27

Приклад 2

Дивіться файли vegetables/vegetables2.in та vegetables/vegetables2.ans у каталозі учасника.

Приклад 3

Дивіться файли vegetables/vegetables3.in та vegetables/vegetables3.ans у каталозі учасника.

Пояснення до прикладу 1

Є два види овочів:

Кожна продана одиниця овочів першого виду приносить дохід $3$, а перший продаж цього виду додатково приносить $3$. Є 3 одиниці цих овочів, і всі вони псуються наприкінці першого дня.

Кожна продана одиниця овочів другого виду приносить дохід $2$, а перший продаж цього виду додатково приносить $5$. Є 8 одиниць цих овочів: 3 псуються наприкінці першого дня, 3 — наприкінці другого, а 2 — наприкінці третього.

Якщо продавати лише протягом одного дня, слід продати 2 одиниці овочів першого виду та 1 одиницю другого.

Тоді дохід від першого виду становить $2\times 3+3$, а від другого — $1\times 2+5$; загальний дохід дорівнює $(2\times 3+3)+(1\times 2+5)=16$.

Якщо продавати протягом трьох днів, то першого дня слід продати 3 одиниці овочів першого виду, другого — 3 одиниці другого виду (вибравши саме ті 3 одиниці, що зіпсуються наприкінці другого дня), а третього — 2 одиниці другого виду.

Тоді дохід від першого виду становить $3\times 3+3$, а від другого — $(3+2)\times 2+5$; загальний дохід дорівнює $(3\times 3+3)+[(3+2)\times 2+5]=27$.

Підзадачі

Властивість 1: усі $s_i$ дорівнюють $0$.

Властивість 2: усі $x_i$ дорівнюють $0$.

У всіх тестах гарантується, що значення $p_j$ у $k$ запитаннях попарно різні.

У всіх тестах гарантується $0<a_i,c_i\le 10^9$, $0\le s_i,x_i\le 10^9$.