1079 - Takenoko Taro - Volume 02

時間制限 1 秒 / メモリ制限 128 MB / 得点 2 / Writer ei1821 / x 2 / 統計 /


TLE
1sec
MLE
128MB
得点
2
テストケース不十分!!!!!

あらすじ


筍太郎は、鬼を退治するために鬼ヶ島(おにがしま)へと出発した。
おばあさんにもらったきび団子を出会ったものたちにあげることで仲間にしていき、鬼ヶ島へたどりつく頃にはすでに筍太郎一派は一師団ほどの軍団となっていた。
しかしそれでも鬼には勝てず、筍太郎は鬼に殺され掛けていた。
そこでおばあさんの目が覚め、今までのことは夢であったことが発覚。しかし予知夢であると判断し、おじいさんと未来のためにきび団子を量生産し万全を期した状態で筍太郎を見送ったのであった。

ストーリー


 筍太郎はおばあさんにきび団子を作ってもらうと、鬼ヶ島へ出かけました。
 旅の途中で、$slave$1に出会いました。
「筍太郎さん、どこへ行くのですか?」
「鬼ヶ島へ、鬼退治に行くんだ」
「それでは、お腰に付けたきび団子を$dump$1つ下さいな。おともしますよ」
 $slave$1はきび団子をもらい、筍太郎のおともになりました。
 そしてこんどは$slave$2に出会いました。
「筍太郎さん、どこへ行くのですか?」
「鬼ヶ島へ、鬼退治に行くんだ」
「それでは、お腰に付けたきび団子を$dump$2つ下さいな。おともしますよ」
 そしてこんどは、$slave$3に出会いました。
「筍太郎さん、どこへ行くのですか?」
「鬼ヶ島へ、鬼退治に行くんだ」
「それでは、お腰に付けたきび団子を$dump$3つ下さいな。おともしますよ」
 そしてこんどは、$slave$iに出会いました。
「筍太郎さん、どこへ行くのですか?」
「鬼ヶ島へ、鬼退治に行くんだ」
「それでは、お腰に付けたきび団子を$dump$iつ下さいな。おともしますよ」
 そしてこんどは、$slave$Nに出会いました。
「筍太郎さん、どこへ行くのですか?」
「鬼ヶ島へ、鬼退治に行くんだ」
「それでは、お腰に付けたきび団子を$dump$Nつ下さいな。おともしますよ」
 $slave$Nにきび団子をあげると、そこでちょうどきび団子はなくなりました。
 筍太郎はおばあさんの予知の凄さに感嘆し、一つつまみ食いしようとしていた自らを叱咤して足を進めます。
 こうして、$slave$1、$slave$2、$slave$3、...、$slave$Nの仲間を手に入れた筍太郎は、ついに鬼ヶ島へやってきました。
 鬼ヶ島では、鬼たちが近くの村からぬすんだ宝物やごちそうをならべて、酒盛りの真っ最中です。
「みんな、ぬかるなよ。それ、かかれ!」
 $dump$aは鬼のおしりにかみつき、$dump$bは鬼のせなかをひっかき、$dump$cはくちばしで鬼の目をつつきました。
 そして筍太郎も、刀をふり回して大あばれです。
 しかし酔いどれであれ、腐っても鬼。
 仲間を大量に引き連れた筍太郎の軍勢を鬼の精鋭たちはなぎ払います。
 数対質の苛烈な争いは三日三晩続き、残るは筍太郎と鬼の親分となりました。
 丸太のような豪腕で振るわれる金棒を、筍太郎は残された右腕と刀のみでそらし、なんとか生き残っています。
 一瞬たりとも気を抜いていられない戦い、劣勢を強いられる筍太郎は退きながら立ち向かいます。
 ステップを踏むように避けていく筍太郎でしたが、何かに足を取られてしまいました。
 バランスを崩しながら何かを確認しようと下を向くと、首のない鬼の死体が転がっていました。
 焦りながらまた鬼の親分の方を向きますが、死体に躓いた絶好の機会を親分は逃すはずがなく。
 筍太郎の頭めがけて金棒が吸い込まれ____


「……はっ!」
 おばあさんは飛ぶように体を起こします。
 肩で息を整えながら周囲の様子を思い出すように、冷や汗をにじませた額をゆっくりと手でさすります。
 なんと、筍太郎の今までの旅は夢だったのです!
 暗闇の中、おばあさんのとなりで眠りについている、まだまだ幼少の筍太郎をおばあさんは見つめ、ほっと息をつきました。
 なんていやな夢だろう、そう思いながら再度布団をかぶり瞼を閉じます。
 しかしなぜだか、おばあさんは夢のことが心配でなりません。
 この悪夢は、本当は予知夢なのではないだろうか。
 深夜に一人で思案していくなかでその心配はふくれあがり、おばあさんは予知夢だとしか思えなくなるほどの自己暗示を掛けてしまいました。
 翌朝、おばあさんは昨晩みた夢の話をおじいさんにしました。
 おじいさんは黙っておばあさんの主張を最後まで聞き、なんと信じてくれました。
「しかしどうすればいいのだろうか」
「筍太郎を旅立たせないというのは?」
「きっと無駄です。筍太郎は黙ってでも出て行くでしょう」
「しかしどうすれば?」
「夢の中できびだんごが足りなくなっていました。全員を仲間に出来るようにたくさんのきびだんごを作りましょう」
「それがよい!」
 しかしおばあさんは一抹の不安がございました。
 夢の中で筍太郎の軍は急ごしらえの数だけ、相手は訓練を重ねた質のよい鬼たち。
 統制がとれていない筍太郎軍は、数を生かし切れず、それどころか足の引っ張り合いをしています。
 本当に全員を連れて行くのがよいのでしょうか。
 おばあさんはそれをおじいさんに伝えます。
「それなら連れて行くものたちを選別していこう!」
「しかし筍太郎はだれを連れて行けばよいかわかりませんし、わたしは筍太郎についていっては足手まといになります」
「筍太郎には、選別の技術を教え込もう」
その案を採用したおじいさんとおばあさんは、その日からきびだんごを作り始め、筍太郎には選別技術をおしえこみました。
 おじいさん直伝の選別技術は、$slave$それぞれが欲するきびだんごの数$dump$iと数値化された戦闘能力$power$iの二つの情報から、保有しているきびだんごで仲間にすることが出来るように選んだ時の戦闘能力の総和を最大にするというものです。
予知夢でN体の$slave$がそれぞれ欲するきびだんごの数と戦闘能力を確認したおばあさんは、筍太郎が成長し旅立つ日までに作れるであろうきびだんごの数を精算します。
「ばあさん、きびだんごはいくつつくればいいんじゃ?」
 おばあさんは総数を伝えると、ふたりともその途方もない数に圧倒されましたが、これも筍太郎の為と気を引き締めてきび団子を作り始めます。


 そしてある日、筍太郎が言いました。
「ぼく、鬼ヶ島(おにがしま)へ行って、わるい鬼を退治します」
「まちなさい、きびだんごだよ。絶対につまみぐいしては駄目だからね」
「きっと鬼ヶ島までの道のりでたくさんのものと出会うだろうが、仲間にするものは選ぶべきだ。
今まで教え込んだ選別技術を駆使して仲間を選ぶのじゃ」  満を持しておばあさんは、きびだんごの山を筍太郎に渡します。
「こんなにたくさんのきびだんご! いったいいくつあるの?」
「うふふ、きび団子は全部でM個だよ」
「おじいさん、おばあさん、ありがとう!」
 そうして筍太郎は鬼ヶ島へ出かけました。
 旅の途中で、$slave$iに出会いました。
「筍太郎さん、どこへ行くのですか?」
「鬼ヶ島へ、鬼退治に行くんだ」
「それでは、お腰に付けたきび団子を$dump$iつ下さいな。おともしますよ」
「あなたの戦闘能力はいくつですか?」
「私の戦闘能力は$power$iです」
「わかりました。あとで判断したいのでついてきてください」
 結局N体の$slave$を従えたまま鬼ヶ島前までたどり着くと、そこで筍太郎は選別を行います。
「決めました。連れて行くのは−−」  そうして仲間にするものの名前を呼びます。
「−−です。そして、総合した戦闘能力は−−−−」
 

入力

1行目に、NとMが与えられる。
2行目以降N行に渡って値$dump$iと$power$iが与えられる。
N  M
$dump$1  $power$1  
$dump$2  $power$2  
...
$dump$N  $power$N

出力

求めた値を一行で出力せよ。 最後の改行を忘れずに。

制約

  • 5 ≤ $N$ ≤ 1000
  • 5 ≤ $M$ ≤ 10000
  • 1 ≤ $dump$i ≤ 10000
  • 1 ≤ $slave$i ≤ 10e7

入出力例

例1

入力

4 5
3 2
2 1
4 3
2 2

出力

4
たった2匹では、鬼は倒せない。
たった4の戦闘能力では、鬼は倒せない。

補足

ei1821は筍派(急進派)である。
ei1821は筍太郎ではない。