Problem J: Rings

Problem

とある水族館に住むイルカ君は、ジャンプをして$N$個のリングをくぐり抜けるとご褒美がもらえます。

• イルカ君は座標$(0,0)$から飛び、$(T,0)$で着水する。
• ジャンプの軌道は放物線である。
• $i$番目のリングは、ジャンプの軌道が$(X_i,L_i)$と$(X_i,H_i)$を結ぶ線分と交わると、くぐり抜けたと判定される。
• $1$回のジャンプには初速と同じだけの体力が必要である。

イルカ君は、必要であれば何度でもジャンプをすることができます。重力加速度ベクトルを$(0,-1)$として、イルカ君が全てのリングを通り抜けるために必要な体力の合計の最小値を求めてください。ただし、摩擦や空気抵抗は無視できるほど小さいとします。

Input

入力は以下の形式で与えられる。

$T$ $N$
$X_1$ $L_1$ $H_1$
$\vdots$
$X_N$ $L_N$ $H_N$

まず$1$行に$T$と$N$が与えられる。その後$N$行に$i$番目のリングの位置、$X_i$、$L_i$、$H_i$が与えられる。

Constraints

入力は以下の条件を満たす。

• 入力はすべて整数である。
• $1 \le X_i < T \le 10^6$
• $1 \le N \le 10^5$
• $1 \le L_i < H_i \le 10^6$

Output

答えを一行に出力する。絶対誤差または相対誤差が$10^{-9}$以下の場合正答と判定される。

Sample Input 1

100 5
50 1 5
50 5 10
50 20 30
50 40 60
50 61 1000000

Sample Output 1

48.6090201099

点$(50,5)$を通るように飛ぶと、$1$番目と$2$番目のリングを同時にくぐることができます。

Sample Input 2

64 15
38 133177 927361
48 177920 668766
12 680425 790550
43 6853 384115
17 214954 723798
62 63843 153825
28 399349 482937
2 336136 367001
33 138008 733496
6 203462 911631
58 321974 527734
17 696940 781678
55 265874 507640
41 56037 880001
34 279422 528651

Sample Output 2

6087.909851326286