يعمل 小 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$، تفسد $x_i$ وحدة من الخضروات في نهاية اليوم $d$.
وبوجه خاص، إذا كان $(d-1)\times x_i \le c_i < d\times x_i$، فإن $c_i-(d-1)\times x_i$ وحدة من الخضروات تفسد في نهاية اليوم $d$.
انتبه إلى أن $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$، يكون عائد كل وحدة $2$، وعند بيع هذا النوع لأول مرة يكون العائد الإضافي $5$. يوجد إجمالا $8$ وحدات من هذا النوع، منها $3$ وحدات تفسد في نهاية اليوم الأول، و$3$ وحدات في نهاية اليوم الثاني، ووحدتان في نهاية اليوم الثالث.
عند البيع ليوم واحد فقط، ينبغي بيع وحدتين من النوع الأول ووحدة واحدة من النوع الثاني.
في هذه الحالة يكون عائد بيع النوع الأول $2\times 3+3$، وعائد بيع النوع الثاني $1\times 2+5$، فيكون العائد الإجمالي $(2\times 3+3)+(1\times 2+5)=16$.
عند البيع لثلاثة أيام فقط، ينبغي بيع $3$ وحدات من النوع الأول في اليوم الأول، و$3$ وحدات من النوع الثاني في اليوم الثاني (نختار هنا بيع الوحدات الثلاث التي ستفسد في نهاية اليوم الثاني)، ووحدتين من النوع الثاني في اليوم الثالث.
في هذه الحالة يكون عائد بيع النوع الأول $3\times 3+3$، وعائد بيع النوع الثاني $(3+2)\times 2+5$، فيكون العائد الإجمالي $(3\times 3+3)+[(3+2)\times 2+5]=27$.
المهام الفرعية
| رقم حالة الاختبار | $n$ | $m$ | $p_j$ | الخاصية 1 | الخاصية 2 |
|---|---|---|---|---|---|
| $1$ | $\le 2$ | $\le 10$ | $\le 10^3$ | لا | لا |
| $2$ | $\le 3$ | $\le 10$ | $\le 10^3$ | لا | لا |
| $3$ | $\le 4$ | $\le 10$ | $\le 10^3$ | لا | لا |
| $4$ | $\le 10^3$ | $\le 10$ | $\le 2$ | لا | لا |
| $5$ | $\le 10^3$ | $\le 10$ | $\le 3$ | لا | لا |
| $6$ | $\le 10^3$ | $\le 10$ | $\le 4$ | لا | لا |
| $7$ | $\le 4$ | $\le 1$ | $\le 4$ | لا | لا |
| $8$ | $\le 6$ | $\le 2$ | $\le 6$ | لا | لا |
| $9$ | $\le 8$ | $\le 1$ | $\le 8$ | لا | لا |
| $10$ | $\le 10$ | $\le 2$ | $\le 10$ | لا | لا |
| $11$ | $\le 20$ | $\le 3$ | $\le 20$ | لا | لا |
| $12$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | نعم | لا |
| $13$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | لا | نعم |
| $14$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | لا | لا |
| $15$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | لا | لا |
| $16$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | نعم | نعم |
| $17$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | نعم | لا |
| $18$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | لا | نعم |
| $19$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | لا | لا |
| $20$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | لا | لا |
| $21$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | نعم | نعم |
| $22$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | نعم | لا |
| $23$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | لا | نعم |
| $24$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | لا | لا |
| $25$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | لا | لا |
الخاصية 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$.