Go: ///
// File:  0579.go
// Author: ymiyamoto
//
// Created on Mon Mar 19 18:46:50 2018
//
package main

import (
	"fmt"
)

var D, N int

type cloth struct {
	A, B, C int
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func main() {
	fmt.Scan(&D, &N)
	thermals := make([]int, D+1)

	for i := 1; i <= D; i++ {
		fmt.Scan(&thermals[i])
	}

	clothes := make([]cloth, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&clothes[i].A, &clothes[i].B, &clothes[i].C)
	}

	dp := make([][]int, D+1)
	for i := range dp {
		dp[i] = make([]int, N)
	}

	for i := 1; i < D; i++ {
		for j := 0; j < N; j++ {
			for k := 0; k < N; k++ {
				t1 := thermals[i]
				t2 := thermals[i+1]
				if clothes[j].A <= t2 && t2 <= clothes[j].B && clothes[k].A <= t1 && t1 <= clothes[k].B {
					dp[i+1][j] = max(dp[i+1][j], dp[i][k]+abs(clothes[j].C-clothes[k].C))
				}
			}
		}
	}

	val := 0
	for _, v := range dp[D] {
		val = max(val, v)
	}

	fmt.Println(val)
}

C++: #include <bits/stdc++.h>

using namespace std;

typedef struct {
	int a;
	int b;
	int c;
} fuku_t;

int d, n;

int t[200];
fuku_t fuku[200];

int dp[200][200];

int main()
{
	cin >> d >> n;

	for (int i = 0; i < d; ++i) cin >> t[i];

	for (int i = 0; i < n; ++i) scanf("%d %d %d", &fuku[i].a, &fuku[i].b, &fuku[i].c);

	for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
		if (fuku[j].a <= t[0] && t[0] <= fuku[j].b && fuku[i].a <= t[1] && t[1] <= fuku[i].b) {
			dp[1][i] = max(dp[1][i], abs(fuku[j].c - fuku[i].c));
		}
	}

	for (int i = 2; i < d; ++i) for (int j = 0; j < n; ++j) for (int k = 0; k < n; ++k) {
		if (fuku[j].a <= t[i] && t[i] <= fuku[j].b && fuku[k].a <= t[i - 1] && t[i - 1] <= fuku[k].b) {
			dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(fuku[k].c - fuku[j].c));
		}
	}

	int ans = 0;

	for (int i = 0; i < n; ++i) ans = max(ans, dp[d - 1][i]);

	printf("%d\n", ans);
}

C++: #include<iostream>
#include<cstdio>
using namespace std;
int abs(int x){
	if(x<0)return -x;
	return x;
}
int main()
{
	int d,n,t[200],a[100],b[100],c[100];
	cin >> d >> n;
	for(int i=0;i<d;i++)cin >> t[i];
	for(int i=0;i<n;i++)cin >> a[i] >> b[i] >> c[i];
	int ans=0;
	for(int i=0;i<d-1;i++){
		int x=0;
		for(int j=0;j<n;j++){
			if(a[j]<=t[i]&&t[i]<=b[j]){
				for(int k=0;k<n;k++){
					if(a[k]<=t[i+1]&&t[i+1]<=b[k]){
						x=max(x,abs(c[k]-c[j]));
					}
				}
			}
		}
		ans+=x;
	}
	cout << ans << "\n";
	return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

struct Clothes{
	int A,B,C;
};

int abso(int n){
	if(n<0) return n*-1;
	return n;
}

int main(){
	Clothes clothes[200];
	int day[201],dp[201][200]={},N,D,ans=0;
	cin>>D>>N;
	for(int i=1;i<=D;i++){
		cin>>day[i];
	}
	for(int i=0;i<N;i++){
		cin>>clothes[i].A>>clothes[i].B>>clothes[i].C;
	}
	for(int i=1;i<D;i++){
		for(int j=0;j<N;j++){
			//printf("%d ",dp[i][j]);
			if(day[i]<clothes[j].A || clothes[j].B<day[i]) continue;
			for(int k=0;k<N;k++){
				if(day[i+1]<clothes[k].A || clothes[k].B<day[i+1]) continue;
				dp[i+1][k]=max(dp[i+1][k], dp[i][j]+abso(clothes[j].C-clothes[k].C));
			}
		}//puts("");
	}
	for(int i=0;i<N;i++){
		//printf("%d ",dp[D][i]);
		ans=max(ans,dp[D][i]);
	}//puts("");
	printf("%d\n",ans);
	return 0;
}

C++: //暑い日々
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<utility>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
#define MP make_pair
#define PB push_back
#define F_d first
#define S_d second
#define LARGE 100000000
#define MOD 100000
#define LL long long

int D, N, T[209], csum[209][3] = {};
vector<int>suit[209];
int main() {
	cin >> D >> N;
	for (int i = 0; i < D; i++)cin >> T[i];
	for (int i = 0; i < N; i++) {
		int a, b, c;  cin >> a >> b >> c;
		for (int j = 0; j < D; j++) {
			if (T[j] >= a && T[j] <= b) {
				suit[j].PB(c);
				//cout << i << " " << j << " " << T[j] << " " << c << endl;
			}
		}
	}

	int MAX[209], MIN[209];
	for (int i = 0; i < D; i++) {
		sort(suit[i].begin(), suit[i].end());
		MAX[i] = suit[i].back();
		MIN[i] = suit[i].front();
		//cout << "MIN = " << MIN[i] << ";  MAX = " << MAX[i] << endl;
	}
	for (int i = 1; i < D; i++) {
		int t1, t2, t3, t4;//NN,NX,XN,XX
		t1 = csum[i - 1][0] + abs(MIN[i - 1] - MIN[i]);
		t2 = csum[i - 1][1] + abs(MAX[i - 1] - MIN[i]);
		t3 = csum[i - 1][0] + abs(MIN[i - 1] - MAX[i]);
		t4 = csum[i - 1][1] + abs(MAX[i - 1] - MAX[i]);
		csum[i][0] = max(t1, t2); csum[i][1] = max(t3, t4);
	}
	cout << max(csum[D - 1][0], csum[D - 1][1]) << endl;

	return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>

using namespace std;

#define rep(i,n) for(int i = 0; i<n ; i++)
#define FOR(i,a,n) for(int i=a; i<n; i++)

#define RANGE(a,i,b) ((a)<=(i)&&(i)<=(b))

#define pb push_back
#define mp make_pair

#define ALL(a) (a).begin(), (a).end()

#define SET(a,c) memset(a,c,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))

#define INF 1001001001
#define LLINF 1001001001001001001LL

typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

#define PQ priority_queue

#define FST first
#define SEC second

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//------------------HEAD---------------------

int dp[200][200];

int D,N;
int A[200],B[200],C[200];
int T[200];
/*
int solve(int d, int a){
    //d??\?????????a??????????????????d????????§
    if(dp[d][a]!=INF){
        return dp[d][a];
    }

    int res=0;

    rep(i,N){
        //d-1??\???????????¶?????????????±???????
        if(RANGE(A[i],T[d],B[i]+1)){
            res=max(res, solve[d-1][i]);
        }
    }
    dp[d][a]=res;

}
*/


int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>D>>N;
    rep(i,D){
        int t;
        cin>>t;
        T[i]=t;
    }
    rep(i,N){
        int a,b,c;
        cin>>a>>b>>c;
        A[i]=a;
        B[i]=b;
        C[i]=c;
    }
    rep(i,D)rep(j,N)dp[i][j]=-INF;

    rep(a,N){
        if(RANGE(A[a],T[0],B[a])){
            dp[0][a]=0;
        }
    }

    FOR(d,1,D){
        rep(a,N){
            if(RANGE(A[a],T[d],B[a])){
                int res=-INF;
                rep(i,N){
                    //d-1??\???????????¶?????????????±???????
                    if(dp[d-1][i]!=-INF){
                        res=max(res, dp[d-1][i]+abs(C[i]-C[a]));
                    }
                }
                dp[d][a]=res; 
            }
        }
    }
    int res=-INF;
    rep(i,N){
        //D??\???????????¶?????????????±???????
        res=max(res, dp[D-1][i]);
        
    }
    cout<<res<<endl; 


    return 0;
}

C++: #include<bits/stdc++.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int main(){
	int n,a,b,k,c[100];
	scanf("%d%d%d%d",&n,&a,&b,&k);
	for(int i=0;i<n;i++) scanf("%d",&c[i]);
	sort(c,c+n);
	int d=a, res=k/d;
	for(int i=n-1;i>=0;i--){
		d+=b;k+=c[i];
		if(res>k/d)break;
		res=k/d;
	}
	printf("%d\n",res);
}

C++: #include <bits/stdc++.h>
using namespace std;
 
int main() {
    int D, N, T[210], A[210], B[210], C[210];
    cin >> D >> N;
    for (int i = 0; i < D; ++i) cin >> T[i];
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i] >> C[i];
 
    int dp[D + 1][N];
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < N; ++i) {
        if (A[i] <= T[0] && T[0] <= B[i]) dp[0][i] = 0;
    }
 
    for (int i = 0; i < D - 1; ++i) {
        for (int j = 0; j < N; ++j) {
            if (dp[i][j] != -1) {
                for (int k = 0; k < N; ++k) {
                    if (A[k] <= T[i + 1] && T[i + 1] <= B[k]) {
                        dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + abs(C[k] - C[j]));
                    }
                }
            }
        }
    }
 
    int ans = 0;
    for (int i = 0; i < N; ++i) ans = max(ans, dp[D - 1][i]);
    cout << ans << endl;
     
    return 0;
}