1158 - World Takenoko -Yggdrasill-
ストーリー
ei1821は筍派(急進派)である。
二次元座標上の原点に世界樹"タケノコ"が存在している。
タケノコは栄養豊富で†無限のエネルギー†を有している。
そして各座標($x$$i$,$y$$i$)にキノコ$K$$i$が存在している。
キノコは各座標から直線でタケノコを目指し、1日1単位距離進む。
座標と距離の関係だが、座標が(1,-1)である場合、原点からx軸方向に1単位距離進みy軸方向に-1単位距離進んだ点であるといえる。
タケノコにたどり着いたキノコは次の日替わりのタイミングから行動を開始する。
$K$$i$は1日で$d$$i$のエネルギーを吸収する。これを永遠に行う。
キノコは$N$体いるが、最終的には$N$体全てがタケノコに群がることになるだろう。
さて、あなたは三次元時空を見下ろす四次元時空の住人です。
キノコは貴方の手下で、養分を規定値まで回収するのがお仕事なのですが、キノコ運用も楽な仕事ではありません。
最近はコストも掛かるようになり、時間も長く取れません。
なのであなたは既定値まで回収できたらさっさと終わらせたいです。他次元時空への干渉は国際法により0:00に行うよう定められているためキノコの帰還は日替わりと同時になります。
さて、$N$体のキノコで$M$の養分を回収するには何日掛かるでしょうか。
入力
1行目に、キノコの数Nと回収したい養分の量Mが空白区切りで与えられる。2行目以降N行に渡ってKiの座標x,yと1日に回収できる養分の量dが空白区切りで与えられる。
N M x1 y1 d1 x2 y2 d2 ... xN yN dN
出力
何日目で帰還できるか、日数を出力せよ。最後の改行を忘れずに。
制約
- 1 ≤ $N$ ≤ 106
- 0 ≤ $M$ ≤ 107
- -50000 ≤ $x$$i$, $y$$i$ ≤ 50000
- 1 ≤ $d$i ≤ 107
- 入力は全て整数
- $x$$i$は0以外もしくは$y$$i$は0以外
- 初期状態、同じ座標にキノコが2体以上いることはない。
入出力例
例1
入力
4 10 1 0 1 3 4 1 3 3 1 7 9 1
出力
81日目、4体のキノコは座標上に降り立ち、同時に進軍を開始した。
1日目と2日目の日替わりと同時に$K$1がタケノコのもとにたどり着いたので、2日目から$K$1は養分吸収を開始する。
本日までの回収は0。
2日目、1体が養分吸収をしている。本日までの回収は1。
3日目、1体が養分吸収をしている。本日までの回収は2。
4日目、1体が養分吸収をしている。本日までの回収は3。
5日目、1体が養分吸収をしている。5日目の途中で$K$3が、その後$K$4がタケノコのもとにたどり着いた。2体は6日目から吸収に参加する。
本日までの回収は4。
6日目、3体が養分吸収をしている。7日目からは吸収数が3へと上昇した。本日までの回収は7。
7日目、3体が養分吸収をしている。本日までの回収は10。
これで養分を合計10回収したので、帰還する。
帰還は次の日替わりと同時なので、8日目に変わった瞬間、4体のキノコは帰還した。なお、$K$4はなにもしていない。
例2
入力
3 0 1 1 1 2 2 2 3 3 3
出力
1回収したい養分は0であるというのに、3体ものキノコを送還してしまった。
回収するものは何もないので送還と同時に帰還、1日で終了である。
おちゃめだ。
例3
入力
3 1 1 1 1 2 2 2 3 3 3
出力
4$K$1が2日目に到着、3日目から吸収開始、4日目に帰還。
例4
入力
1 10000000 -50000 -50000 1
出力
10070712
補足
タケノコは世界樹であるため、何よりも太く何よりも高い、何よりも大きな存在であるが、原点にのみ存在するため面積や体積はない。