N kecil adalah pengelola sebuah gudang sayuran yang bertanggung jawab menyusun rencana penjualan sayuran.
Gudang tersebut menyimpan $n$ jenis sayuran. N kecil harus mempertimbangkan berbagai faktor berdasarkan karakteristik setiap jenis sayuran untuk merancang rencana penjualan yang masuk akal dan memperoleh pendapatan sebesar mungkin.
Dalam perhitungan pendapatan penjualan sayuran, setiap penjualan satu unit sayuran jenis ke-$i$ memberikan pendapatan $a_i$.
Secara khusus, karena kebijakan mendorong pedagang menjual beragam jenis barang, penjualan pertama sayuran jenis ke-$i$ juga memberikan pendapatan tambahan sebesar $s_i$.
Pada awal usaha, persediaan sayuran jenis ke-$i$ adalah $c_i$ unit.
Namun, masa kesegaran sayuran sangat terbatas. Setelah membusuk, sayuran tidak dapat dijual. N kecil yang cerdas sudah menghitung waktu pembusukan setiap unit sayuran: untuk sayuran jenis ke-$i$, terdapat nilai kesegaran $x_i$, dan pada akhir setiap hari ada $x_i$ unit sayuran yang membusuk hingga semuanya membusuk. (Perhatikan: waktu pembusukan setiap unit sayuran tetap dan tidak berubah akibat penjualan.)
Secara formal: untuk setiap bilangan bulat positif $d$ yang memenuhi $d\times x_i\le c_i$, terdapat $x_i$ unit sayuran yang akan membusuk pada akhir hari ke-$d$.
Secara khusus, jika $(d-1)\times x_i\le c_i<d\times x_i$, terdapat $c_i-(d-1)\times x_i$ unit sayuran yang akan membusuk pada akhir hari ke-$d$.
Perhatikan bahwa ketika $x_i=0$, sayuran jenis ini tidak akan membusuk.
Selain itu, jumlah total sayuran yang dapat dijual setiap hari juga terbatas, yaitu tidak boleh melebihi $m$ unit.
Sekarang, N kecil memiliki $k$ pertanyaan yang ingin kamu bantu hitung. Setiap pertanyaan berbentuk: untuk $p_j$ yang diketahui, jika penjualan berlangsung selama $p_j$ hari, berapa pendapatan maksimum yang dapat diperoleh?
Masukan
Baca data dari berkas vegetables.in.
Baris pertama berisi tiga bilangan bulat positif $n,m,k$, yang berturut-turut menyatakan banyaknya jenis sayuran, batas atas jumlah total sayuran yang dapat dijual setiap hari, dan banyaknya pertanyaan N kecil.
Masing-masing dari $n$ baris berikutnya berisi empat bilangan bulat nonnegatif yang mendeskripsikan karakteristik satu jenis sayuran, berturut-turut $a_i,s_i,c_i,x_i$, dengan arti yang diberikan di atas.
Masing-masing dari $k$ baris berikutnya berisi sebuah bilangan bulat nonnegatif $p_j$, dengan arti yang diberikan di atas.
Keluaran
Tulis keluaran ke berkas vegetables.out.
Keluarkan $k$ baris, masing-masing berisi sebuah bilangan bulat. Bilangan pada baris ke-$i$ menyatakan jawaban pertanyaan ke-$i$.
Contoh
Masukan 1
2 3 2 3 3 3 3 2 5 8 3 1 3
Keluaran 1
16 27
Contoh 2
Lihat vegetables/vegetables2.in dan vegetables/vegetables2.ans dalam direktori peserta.
Contoh 3
Lihat vegetables/vegetables3.in dan vegetables/vegetables3.ans dalam direktori peserta.
Penjelasan Contoh 1
Ada dua jenis sayuran:
Saat menjual sayuran jenis pertama, pendapatan per unit adalah $3$, dan penjualan pertama jenis sayuran ini memberikan pendapatan tambahan $3$. Ada $3$ unit sayuran jenis ini, dan semuanya membusuk pada akhir hari pertama.
Saat menjual sayuran jenis kedua, pendapatan per unit adalah $2$, dan penjualan pertama jenis sayuran ini memberikan pendapatan tambahan $5$. Ada $8$ unit sayuran jenis ini: $3$ unit membusuk pada akhir hari pertama, $3$ unit pada akhir hari kedua, dan $2$ unit pada akhir hari ketiga.
Jika penjualan hanya berlangsung 1 hari, sebaiknya menjual $2$ unit sayuran jenis pertama dan $1$ unit sayuran jenis kedua.
Dalam keadaan ini, pendapatan penjualan sayuran jenis pertama adalah $2\times 3+3$; pendapatan penjualan sayuran jenis kedua adalah $1\times 2+5$; dan total pendapatan adalah $(2\times 3+3)+(1\times 2+5)=16$.
Jika penjualan hanya berlangsung 3 hari, pada hari pertama sebaiknya menjual $3$ unit sayuran jenis pertama, pada hari kedua menjual $3$ unit sayuran jenis kedua (pilih $3$ unit yang akan membusuk pada akhir hari kedua untuk dijual), dan pada hari ketiga menjual $2$ unit sayuran jenis kedua.
Dalam keadaan ini, pendapatan penjualan sayuran jenis pertama adalah $3\times 3+3$; pendapatan penjualan sayuran jenis kedua adalah $(3+2)\times 2+5$; dan total pendapatan adalah $(3\times 3+3)+[(3+2)\times 2+5]=27$.
Subtugas
| Nomor kasus uji | $n$ | $m$ | $p_j$ | Sifat 1 | Sifat 2 |
|---|---|---|---|---|---|
| $1$ | $\le 2$ | $\le 10$ | $\le 10^3$ | Tidak | Tidak |
| $2$ | $\le 3$ | $\le 10$ | $\le 10^3$ | Tidak | Tidak |
| $3$ | $\le 4$ | $\le 10$ | $\le 10^3$ | Tidak | Tidak |
| $4$ | $\le 10^3$ | $\le 10$ | $\le 2$ | Tidak | Tidak |
| $5$ | $\le 10^3$ | $\le 10$ | $\le 3$ | Tidak | Tidak |
| $6$ | $\le 10^3$ | $\le 10$ | $\le 4$ | Tidak | Tidak |
| $7$ | $\le 4$ | $\le 1$ | $\le 4$ | Tidak | Tidak |
| $8$ | $\le 6$ | $\le 2$ | $\le 6$ | Tidak | Tidak |
| $9$ | $\le 8$ | $\le 1$ | $\le 8$ | Tidak | Tidak |
| $10$ | $\le 10$ | $\le 2$ | $\le 10$ | Tidak | Tidak |
| $11$ | $\le 20$ | $\le 3$ | $\le 20$ | Tidak | Tidak |
| $12$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | Ya | Tidak |
| $13$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | Tidak | Ya |
| $14$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | Tidak | Tidak |
| $15$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | Tidak | Tidak |
| $16$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Ya | Ya |
| $17$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Ya | Tidak |
| $18$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Tidak | Ya |
| $19$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Tidak | Tidak |
| $20$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Tidak | Tidak |
| $21$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Ya | Ya |
| $22$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Ya | Tidak |
| $23$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Tidak | Ya |
| $24$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Tidak | Tidak |
| $25$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Tidak | Tidak |
Sifat 1: semua $s_i$ bernilai $0$.
Sifat 2: semua $x_i$ bernilai $0$.
Untuk semua data uji, dijamin bahwa $p_j$ dalam $k$ pertanyaan saling berbeda.
Untuk semua data uji, dijamin $0<a_i,c_i\le 10^9$ dan $0\le s_i,x_i\le 10^9$.