noi2017-Day2-T2
【問題描述】
小N是蔬菜倉庫的管理員帝际，負責(zé)設(shè)計蔬菜的銷售方案。
在蔬菜倉庫中饶辙，共存放有n種蔬菜蹲诀，小N需要根據(jù)不同蔬菜的特性，綜合考慮各方面因素弃揽，設(shè)計合理的銷售方案脯爪，以獲得最多的收益。
在計算銷售蔬菜的收益時矿微，每銷售一個單位第i種蔬菜痕慢，就可以獲得ai的收益。
特別地涌矢，由于政策鼓勵商家進行多樣化銷售掖举，第一次銷售第i種蔬菜時，還會額外得到si的額外收益娜庇。
在經(jīng)營開始時塔次，第i種蔬菜的庫存為ci個單位方篮。
然而，蔬菜的保鮮時間非常有限励负，一旦變質(zhì)就不能進行銷售藕溅，不過聰明的小N已經(jīng)計算出了每個單位蔬菜變質(zhì)的時間 ：對于第i種蔬菜，存在保鮮值xi熄守，每天結(jié)束時會有xi個單位的蔬菜變質(zhì)蜈垮，直到所有蔬菜都變質(zhì)耗跛。（注意：每一單位蔬菜的變質(zhì)時間是固定的裕照，不隨銷售發(fā)生變化）
形式化地：對于所有的滿足條件d * xi <= ci的正整數(shù)d,有xi個單位的蔬菜將在第d天結(jié)束時變質(zhì)。
特別地调塌，若(d-1)xi <= ci < dxi,則有ci - (d - 1)*xi單位的蔬菜將在第d天結(jié)束時變質(zhì)晋南。
注意，當(dāng) xi=0時羔砾，意味著這種蔬菜不會變質(zhì)负间。
同時，每天銷售的蔬菜總量也是有限的姜凄，最多不能超過m個單位政溃。
現(xiàn)在，小N有k個問題态秧，想請你幫忙算一算董虱。每個問題的形式都是：對于已知的pj，如果需要銷售pj天申鱼，最多能獲得多少收益愤诱？
（題目描述以pdf文件為準(zhǔn)）
【輸入形式】
從文件 vegetables.in 中讀入數(shù)據(jù)。 第一行包含三個正整數(shù) n, m, k,分別表示蔬菜的種類數(shù)目捐友、每天能售出蔬菜總量上限淫半、小 N 提出的問題的個數(shù)。 接下來 n 行,每行輸入四個非負整數(shù),描述一種蔬菜的特點,依次為 a i , s i , c i , x i ,意義如上文所述匣砖。 接下來 k 行,每行輸入一個非負整數(shù) p j ,意義如上文所述科吭。
【輸出形式】
輸出到文件 vegetables.out 中。 輸出 k 行,每行包含一個整數(shù),第 i 行的數(shù)表示第 i 個問題的答案猴鲫。
【輸入樣例1】
見下發(fā)文件的 vegetables/vegetables1.in砌溺。
【輸出樣例1】
見下發(fā)文件的 vegetables/vegetables1.ans。
【輸入樣例2】
見下發(fā)文件的 vegetables/vegetables2.in变隔。
【輸出樣例2】
見下發(fā)文件的 vegetables/vegetables2.ans规伐。
【輸入樣例3】
見下發(fā)文件的 vegetables/vegetables3.in。
【輸出樣例3】
見下發(fā)文件的vegetables/vegetables3.ans匣缘。
【時間限制】
3s
【空間限制】
512000KB
【上傳文件】
上傳c, cpp, pas語言源程序猖闪，文件名為vegetables.c, vegetables.cpp, vegetables.pas鲜棠。
Upload Your source File(s) :
Note :Your program can be written with the programing language(s) as below
C(.c): your source filename is ''vegetables.c''
CPP(.cpp): your source filename is ''vegetables.cpp''
PAS(.pas): your source filename is ''vegetables.pas''
我知道是用貪心的策略，
但無論是單獨貪心多賣還是單獨貪心高價明顯都會有對應(yīng)的數(shù)據(jù)卡分培慌，
明智的貪心顯然會是其他辦法,我暫時沒有思路豁陆，做過類似的例題，模擬賽中一時記不得了
