Oversleeping, again

2 secs 1024 MB
hirono999

問題文


高橋くんは,時刻の時点で個の目覚まし時計をかけて眠っています.

番目の目覚まし時計は時刻から分後に初めて鳴り始め,さらに分ごとに鳴り始めるようにセットされています.

どの目覚まし時計も一度鳴り始めると分間鳴り続けます.

より厳密には,について,番目の時計はをみたす時刻の間だけ鳴ります.

また,番目の目覚まし時計の音量はにセットされています.

同時に鳴っている目覚まし時計の音量の合計が初めて以上になったとき,高橋くんは目を覚まします.

高橋くんが目を覚ますか判定し,目を覚ますならば時刻から何分後であるかを求めてください.

なお,この値はこの問題の制約下で整数になることが証明できます.

制約


  • 入力は全て整数

入力


入力はすべて整数である.





出力


高橋くんが目を覚ます時刻を出力せよ. ただし,高橋くんが目を覚ますことが無い場合は,-1を出力せよ.

サンプル


入力1
1 1
10 1 1
出力1
10

番目の時計が時刻に音量で鳴り始めた時点で,高橋くんは目を覚まします.

入力2
3 24
2 3 5
7 5 9
9 8 10
出力2
17
入力3
3 15
2 3 1
7 5 1
9 8 1
出力3
-1

目覚まし時計の音量が足りていないことがあります.

提出


Go (1.14)