#include #include #include #include #include #include #include #include #include #include #include #include #include #include // std::stringstream #include #include using namespace atcoder; using mint = modint998244353; //using mint = modint1000000007; using namespace std; using ll = long long; static const double pi = 3.141592653589793; const int INF = (1 << 29); const ll mod = 998244353; // ifstream ifs(""); ファイルはワークスペースのトップにおく int main() { int n,m; cin >> n >> m; vector L(n); for(int i=0;i> L[i]; ll ans = 0; while(m--){ int f,b,w; cin >> f >> b >> w; int lb = lower_bound(L.begin(),L.end(),f)-L.begin(); int ub = upper_bound(L.begin(),L.end(),f)-L.begin(); if(lb==n) lb--; if(ub==n) ub--; int cost = min(abs(f-L[lb]),abs(f-L[ub])); if(cost == 0){ //湖にいる ans += w; }else{ //陸にいる ans += max(w-cost,b); } } cout << ans << endl; }