新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:65536KB
問題 
牛は世界的に有名なヤッキーヨーグルトのヨーグルト工場を買いました。次のN(1<=N<=10000)週の間、原料のミルクを買い、ヨーグルトを作るのに第i週においてC_i(1<=C_i<=5000)セントかかります。ヤッキーの工場はとてもたくさんのヨーグルトを各週に作ることができます。
ヤッキーヨーグルトは倉庫にヨーグルトを保管しておくのに１週間につきS(1<=S<=100)セントの料金がかかります。また、ヨーグルトが腐ることはありません。ヤッキーヨーグルトの倉庫は巨大で、とてもたくさんのヨーグルトを保管することができます。
ヤッキーは第i週にはY_i(0<=Y_i<=10000)個のヨーグルトを出荷する方法を見つけたいと思っています。ヤッキーがN週の間を通して最小のコストで出荷できる方法を探すのを手伝ってください。ヨーグルトを第i週につくったとき、それが既に倉庫にあるヨーグルトよりもより良いものであるならば、そのヨーグルトをその週のうちに出荷することができます。
入力
1行目：NとSが空白に区切られて与えられます。
2~N+1行目:i+1行目にC_iとY_iが空白に区切られて与えられます。
出力
１行にN週の間ヨーグルトを出荷するのに必要な最小のコストを出力してください。ただしこの答えは32bit整数より大きくなる場合があります。
サンプル入力
4 5 88 200 89 400 97 400 91 500
サンプル出力
126900
ヒント
出力の説明：
1週目に、200個のヨーグルトを生産しすべて出荷します。2週目には700個生産し、うち400個は出荷、300個は保管します。3週目には、保管してある300個を出荷します。そして最後の週に500個生産しその全てを出荷します。
出典
USACO 2005 March Gold
