問題文

高橋くんは，時刻$0$の時点で$N$個の目覚まし時計をかけて眠っています．

$i$番目の目覚まし時計は時刻$0$から$A_i$分後に初めて鳴り始め，さらに$B_i$分ごとに鳴り始めるようにセットされています．

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

より厳密には，$n = 0, 1, 2, \dots$について，$i$番目の時計は$A_i +B_in \leq t < A_i + B_in + 0.5$をみたす時刻$t$の間だけ鳴ります．

また，$i$番目の目覚まし時計の音量は$C_i$にセットされています．

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

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

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

制約

• 入力は全て整数
• $1 \leq N \leq 10$
• $1 \leq K \leq 10^5$
• $1 \leq A_i, B_i \leq 30$
• $1 \leq C_i \leq 10^5$

入力

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

出力

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

サンプル

1 1
10 1 1

10

$1$番目の時計が時刻$10$に音量$1$で鳴り始めた時点で，高橋くんは目を覚まします．

3 24
2 3 5
7 5 9
9 8 10

17

3 15
2 3 1
7 5 1
9 8 1

-1

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