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 หน่วยเมื่อสิ้นสุดวันที่สาม
หากขายเพียง 1 วัน ควรขายผักชนิดแรก 2 หน่วย และผักชนิดที่สอง 1 หน่วย
ในกรณีนี้ รายได้จากผักชนิดแรกคือ $2\times 3+3$ รายได้จากผักชนิดที่สองคือ $1\times 2+5$ และรายได้ทั้งหมดคือ $(2\times 3+3)+(1\times 2+5)=16$
หากขายเพียง 3 วัน ในวันแรกควรขายผักชนิดแรก 3 หน่วย ในวันที่สองควรขายผักชนิดที่สอง 3 หน่วย (โดยเลือกขาย 3 หน่วยที่จะเน่าเสียเมื่อสิ้นสุดวันที่สอง) และในวันที่สามขายผักชนิดที่สอง 2 หน่วย
ในกรณีนี้ รายได้จากผักชนิดแรกคือ $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$