Problem: Problem

A dolphin who lives in a certain aquarium will be rewarded if he jumps and goes through the $ N $ ring.

* Dolphin jumps from coordinates $ (0,0) $ and lands at $ (T,0) $.
* The trajectory of the jump is a parabola.
* The $ i $ th ring is determined to have passed through when the jump trajectory intersects the line segment connecting $ (X_i, L_i) $ and $ (X_i, H_i) $.
* $ 1 $ jump requires as much physical strength as the initial velocity.



Dolphins can jump as many times as they want. Let the gravitational acceleration vector be $ (0, -1) $ and find the minimum total physical strength required for the dolphin to pass through all the rings. However, suppose friction and air resistance are negligibly small.

Constraints

The input satisfies the following conditions.

* All inputs are integers.
* $ 1 \ le X_i <T \ le 10 ^ 6 $
* $ 1 \ le N \ le 10 ^ 5 $
* $ 1 \ le L_i <H_i \ le 10 ^ 6 $

Input

The input is given in the following format.


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


First, $ T $ and $ N $ are given to the $ 1 $ line. Then the $ N $ line is given the position of the $ i $ th ring, $ X_i $, $ L_i $, and $ H_i $.

Output

Output the answer on one line. If the absolute error or relative error is $ 10 ^ {-9} $ or less, the answer is judged to be correct.

Examples

Input

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


Output

48.6090201099


Input

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


Output

6087.909851326286

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

// chmax, chmin
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

// debug stream of pair, vector
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }


// 有理数
template<typename T> class Rational {
private:
    static Rational make(const T& x, const T& y){
        Rational m; return m.num = x, m.den = y, m;
    }
public:
    friend ostream& operator<<(ostream& os, const Rational& rn) {
        return (os << rn.num << " / " << rn.den);
    }
    Rational& operator=(T val){ return *this = Rational(val); }
    bool operator<(const Rational& val) const { return num*val.den < den*val.num; }
    bool operator<(const T val) const { return *this < Rational(val); }
    friend bool operator<(const T val1, const Rational& val2){ return Rational(val1) < val2; }
    bool operator>(const Rational& val) const { return val < *this; }
    bool operator>(const T val) const { return *this > Rational(val); }
    friend bool operator>(const T val1, const Rational& val2){ return Rational(val1) > val2; }
    bool operator<=(const Rational& val) const { return !(*this > val); }
    bool operator<=(const T val) const { return *this <= Rational(val); }
    friend bool operator<=(const T val1, const Rational& val2){ return Rational(val1) <= val2; }
    bool operator>=(const Rational& val) const { return !(*this < val); }
    bool operator>=(const T val) const { return *this >= Rational(val); }
    friend bool operator>=(const T val1, const Rational& val2){ return Rational(val1) >= val2; }
    bool operator==(const Rational& val) const { return num*val.den == den*val.num; }
    bool operator==(const T val) const { return *this == Rational(val); }
    friend bool operator==(const T val1, const Rational& val2){ return Rational(val1) == val2; }
    bool operator!=(const Rational& val) const { return !(*this == val); }
    bool operator!=(const T val) const { return *this != Rational(val); }
    friend bool operator!=(const T val1, const Rational& val2){ return Rational(val1) != val2; }
    explicit operator bool() const noexcept { return num; }
    bool operator!() const noexcept { return !static_cast<bool>(*this); }
    Rational operator+() const { return *this; }
    Rational operator-() const { return make(-num, den); }
    friend Rational abs(const Rational& val){ return make(abs(val.num), val.den); }
    Rational operator+(const Rational& val) const { return make(num*val.den+val.num*den, den*val.den); }
    Rational operator+(T val) const { return *this + Rational(val); }
    friend Rational operator+(T a, const Rational& b){ return b + a; }
    Rational& operator+=(const Rational& val){ return *this = *this + val; }
    Rational& operator+=(const T& val){ return *this = *this + val; }
    Rational& operator++(){ return *this += 1; }
    Rational operator++(int){ return make(num + den, den); }
    Rational operator-(const Rational& val) const { return make(num*val.den-val.num*den, den*val.den); }
    Rational operator-(T val) const { return *this - Rational(val); }
    friend Rational operator-(T a, const Rational& b){ return Rational(a) - b; }
    Rational& operator-=(const Rational& val){ return *this = *this - val; }
    Rational& operator-=(const T& val){ return *this = *this - val; }
    Rational& operator--(){ return *this -= 1; }
    Rational operator--(int){ return make(num - den, den); }
    Rational operator*(const Rational& val) const { return make(num*val.num, den*val.den); }
    Rational operator*(T val) const { return *this * Rational(val); }
    friend Rational operator*(T a, const Rational& b){ return b * a; }
    Rational& operator*=(const Rational& val){ return *this = *this * val;}
    Rational& operator*=(const T& val){ return *this = *this * val; }
    Rational operator/(const Rational& val) const { return make(num*val.den, den*val.num); }
    Rational operator/(T val) const { return *this / Rational(val); }
    friend Rational operator/(T a, const Rational& b){ return Rational(a) / b; }
    Rational& operator/=(const Rational& val){ return *this / val; }
    Rational& operator/=(const T& val){ return *this = *this / val; }

    T num, den;

    Rational(){}
    Rational(T num_) : num(num_), den(1){}
    Rational(T num_, T den_) : num(num_), den(den_){ if(den < 0) num = -num, den = -den; }
};

long double cost(const Rational<long long> &f, long long T) {
    long double df = (long double)f.num/f.den;
    return sqrt(df * T * T / 2 + 0.5 / df);
}

int main() {
    long long T; int N;
    cin >> T >> N;
    const Rational<long long> center(1, T); // 45 度打ち出しの場合
    using pf = pair<Rational<long long>,Rational<long long>>;
    vector<pf> upper, lower, middle;
    for (int i = 0; i < N; ++i) {
        long long x, low, up; cin >> x >> low >> up;
        Rational<long long> flow(low, x * (T-x));
        Rational<long long> fup(up, x * (T-x));
        if (fup < center) lower.push_back({flow, fup});
        else if (flow > center) upper.push_back({flow, fup});
        else middle.push_back({flow, fup});
    }
    sort(lower.begin(), lower.end(), [](const pf &a, const pf &b) {
            return a.second < b.second;});
    sort(upper.begin(), upper.end(), [](const pf &a, const pf &b) {
            return a.first > b.first;});

    long double res = 0.0;
    Rational<long long> left = 0, right = 1000100; // right * 10^12/4 がオーバーフローしないように
    for (auto inter : lower) {
        if (left >= inter.first) continue;
        res += cost(inter.second, T);
        left = inter.second;
    }
    for (auto inter : upper) {
        if (right <= inter.second) continue;
        res += cost(inter.first, T);
        right = inter.first;
    }
    bool remain = false;
    for (auto inter : middle) {
        if (left < inter.first && inter.second < right) remain = true;
    }
    if (remain) res += cost(center, T);
    cout << fixed << setprecision(20) << res << endl;
}