問題
oさんは食べ放題のレストランに来ている。このレストランでは、お皿の上にできるだけ高く料理を積み上げることが求められる。
いまここで、oさんは幅 $W$ マスの皿を持っており、この上に $N$ 個の料理を積み上げていく。
$i$ 番目($1 \leq i \leq N$)に積む料理は その高さが $H_i$ マス分であり、 皿上の左側から $L_i$ 番目のマスから $R_i$ 番目のマスの部分のうち、
最も高い位置にある料理、または皿面自体にくっつき、重力などで傾いたり崩れたりすることはない。また、この世界では奥行きを考える必要もない。
$N$ 個の料理を積み終わった後に最も上面の位置が高い料理について、その料理が皿面から何マス分高いか求めよ。
入力
入力は以下の形式で標準入力から与えられる。
$W$ $N$ $H_1$ $L_1$ $R_1$ $H_2$ $L_2$ $R_2$ ... $H_N$ $L_N$ $R_N$
1行目に皿の幅 $W$ と、 料理の数 $N$ が与えられる。
次の $N$ 行では、料理の高さと、料理を積む位置が与えられる。具体的には、
$i$ 番目($1 \leq i \leq N$)の料理の高さは $H_i$ で、 皿上の左側から $L_i$ 番目のマスから $R_i$ 番目のマスの部分に積まれる。
出力
$N$ 個の料理を積み終わった後に最も上面の位置が高い料理について、その料理が皿面から何マス分高いかを出力せよ。出力の最後に改行すること。
制約
全ての入出力ケースについて以下を満たす。
- $ 1\leq W \leq 10^{5}$
- $ 1\leq N \leq 10^{4}$
- $ 1\leq L_i \leq R_i \leq W$
- $ 1\leq H_i \leq 10^{9}$
入出力例
入力例1
3 3 1 1 3 1 1 1 1 1 3
出力例1
3
この例の状況を図示すると、次の通り。(Xが料理の位置,oが空白)
XXX
Xoo
XXX
物理法則を無視した積み方もありえる。
入力例2
3 3 2 1 2 1 3 3 1 2 3
出力例2
3
この例の状況を図示すると、次の通り。(Xが料理の位置,oが空白)
oXX
XXo
XXX
料理は順番に積まれることに留意せよ。
入力例3
5 6 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 1 1 5
出力例3
6
この例の状況を図示すると、次の通り。(Xが料理の位置,oが空白)
XXXXX
ooooX
oooXX
ooXXX
oXXXX
XXXXX