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 <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)

int main(void){
	int d, n;//??\??°??????????¨????
	cin >> d >> n;
	vector<int> t(d);
	rep(i, d) cin >> t[i];
	vector<int> a(n), b(n), c(n);//??????????????§????´???????
	rep(i, n) cin >> a[i] >> b[i] >> c[i];

	int dp[201][201];//dp[i][j] i(0~d-1)??\??????j(0~n-1)????????????????????????????????§???
	rep(i, 201)rep(j, 201) dp[i][j] = -1;//?????????
	//0??\?????????????????????dp???0?????\??????
	rep(j, d){
		if(a[j] <= t[0] && t[0] <= b[j]){
			dp[0][j] = 0;
		}
	}
	reps(i, 1, d){//??\
		rep(j, n){//????????????
			rep(k, n){//?????????????????¨??¢?´¢??§??¢????????????
				if(a[k] <= t[i] && t[i] <= b[k] && dp[i - 1][j] != -1){
					dp[i][k] = max(dp[i][k], dp[i - 1][j] + abs(c[k] - c[j]));
				} 
			}
		}
	}


	int ans = 0;
	rep(i, n){
		ans = max(ans, dp[d - 1][i]);
	}
	printf("%d\n", ans);
	return 0;
}

C++: #include <stdio.h>
#include <algorithm>

int D, N, T[212], A[212], B[212], C[212];
int dp[212][212], memo[212], ans;

int main(void) {
	scanf("%d%d", &D, &N);
	for (int i = 0; i < D; ++i) { scanf("%d", &T[i]); }
	for (int i = 0; i < N; ++i) { scanf("%d%d%d", &A[i], &B[i], &C[i]); }

	for (int i = 0; i < D; ++i) {
		for (int j = 0; j < N; ++j) {
			dp[i][j] = -1;
		}
	}
	for (int i = 0; i < D; ++i) {
		for (int j = 0; j < N; ++j) {
			if (A[j] <= T[i] && T[i] <= B[j]) {
				if (i == 0) { dp[i][j] = C[j]; }
				else {
					for (int k = 0; k < N; ++k) {
						if (dp[i - 1][k] != -1) {
							dp[i][j] = dp[i - 1][k] + abs(C[k] - C[j]);
							memo[i] = std::max(memo[i], abs(dp[i][j] - dp[i - 1][k]));
						}
					}
				}
			}
		}
	}

	for (int i = 0; i < D; ++i) {
		ans += memo[i];
	}
	printf("%d\n", ans);
	return 0;
}

C++: #include <iostream>
#include <cmath>
using namespace std;

int main(){
	int d,n,t[200],a[200],b[200],c[200];
	int dp[201][200] = {};
	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];
	for(int i = 1;i <= d;i++){
		for(int j = 0;j < n;j++){
			if(a[j] <= t[i - 1] && t[i - 1] <= b[j]){
				for(int k = 0;k < n;k++){
					if(i >= 2 && a[k] <= t[i - 2] && t[i - 2] <= b[k]) dp[i][j] = max(dp[i][j],dp[i - 1][k] + abs(c[j] - c[k]));
				}
			}
		}
	}
	int ma = 0;
	for(int i = 0;i < n;i++) ma = max(ma,dp[d][i]);
	cout << ma << endl;
	return 0;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
const int A=0;
const int B=1;
const int C=2;
const int INF=45451919;
int D,N;
int temp[201],huku[201][3];
int dp[201][201];


int main(){
	cin>>D>>N;
	for(int i=1;i<=D;i++)cin>>temp[i];
	for(int i=1;i<=N;i++)cin>>huku[i][A]>>huku[i][B]>>huku[i][C];
	//for(int i=1;i<=N;i++)cout<<huku[i][A]<<huku[i][B]<<huku[i][C]<<endl;
	for(int i=0;i<201;i++)for(int j=0;j<201;j++)dp[i][j]=-1;
	for(int i=1;i<=N;i++)if(huku[i][A]<=temp[1]&&huku[i][B]>=temp[1])dp[1][i]=0;
	
	
//		for(int j=0;j<10;j++)
//	cout<<huku[j][C]<<"  ";
//	cout<<endl;
	
for(int i=1;i<=D;i++){
	for(int j=1;j<=N;j++){
		if(huku[j][A]<=temp[i]&&huku[j][B]>=temp[i]&&dp[i][j]!=-1){
			for(int k=1;k<=N;k++){
				if(huku[k][A]<=temp[i+1]&&huku[k][B]>=temp[i+1]){
					dp[i+1][k]=max(abs(huku[k][C]-huku[j][C])+dp[i][j],dp[i+1][k]);
					}
			}
		}
	}
}
	//デバッグ
		/*for(int i=1;i<=D;i++){
		for(int j=1;j<=N;j++){
			cout<<dp[i][j]<<" ";
		}*/
		int ans=0;
		for(int i=1;i<=N;i++)ans=max(ans,dp[D][i]);
			cout<<ans<<endl;
	
return 0;
}

C++: #include <iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
	int d, n;
	cin >> d >> n;
	vector<int> t(d);
	for (int i = 0; i < d; i++) {
		cin >> t[i];
	}
	vector<int>mi(n);
	vector<int>ma(n);
	vector<int>hi(n);
	for (int i = 0; i < n; i++) {
		cin >> mi[i] >> ma[i] >> hi[i];
	}
	vector<int> ha(n, -1);
	int te = t[0];
	for (int i = 0; i < n; i++) {
		if (mi[i] <= te and te <= ma[i]) {
			ha[i] = 0;
		}
		
	}
	for (int i = 1; i < d; i++) {
		int te = t[i];
		vector<int> yob(n);
		yob = ha;
		for (int j = 0; j < n; j++) {
			int a = mi[j];
			int b = ma[j];
			if (a <= te and te <= b) {
				ha[j] = 0;
				for (int k = 0; k < n; k++) {
					if (yob[k]!=-1) {
						ha[j] = max(ha[j], yob[k] + abs(hi[k] - hi[j]));
					}
				}
			}
			else {
				ha[j] = -1;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans = max(ans, ha[i]);
	}
	cout << ans << endl;
}

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

int main() {
  int D, N;
  cin >> D >> N;
  vector<int> T(D);
  for(auto& i: T) cin >> i;
  vector<int> A(N), B(N), C(N);
  for(int j = 0; j < N; ++j) cin >> A[j] >> B[j] >> C[j];

  vector<int> cur(N);
  for(int i = 0; i < D - 1; ++i) {
    vector<int> nex(N);
    for(int j = 0; j < N; ++j) if(A[j] <= T[i] && T[i] <= B[j])
      for(int nj = 0; nj < N; ++nj) if(A[nj] <= T[i + 1] && T[i + 1] <= B[nj])
        nex[nj] = max(nex[nj], cur[j] + abs(C[j] - C[nj]));
    cur = nex;
  }

  cout << *max_element(begin(cur), end(cur)) << endl;
}

C++: #include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	int d,n;
	int t[210],a[210],b[210],c[210],dp[210][210];
	bool suit[210][210];
	scanf("%d%d",&d,&n);
	for(int i=0;i<d;i++){
		scanf("%d",&t[i]);
	}
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
	}
	for(int i=0;i<d;i++)for(int j=0;j<n;j++){
		suit[i][j]=(a[j]<=t[i]&&t[i]<=b[j]);
	}
	for(int i=0;i<d;i++)for(int j=0;j<n;j++){
		dp[i][j]=-1;
	}
	for(int j=0;j<n;j++){
		if(suit[0][j])dp[0][j]=0;
	}
	for(int i=0;i<d-1;i++){
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				if(suit[i+1][k]){
					if(dp[i+1][k]<dp[i][j]+abs(c[j]-c[k])){
						dp[i+1][k]=dp[i][j]+abs(c[j]-c[k]);
					}
				}
			}
		}
	}
	int ans=-1;
	for(int j=0;j<n;j++){
		if(ans<dp[d-1][j])ans=dp[d-1][j];
	}
	printf("%d\n",ans);
	return 0;
}

C++: #include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

#define INF 0x7fffffff

int d;
int n;
int a[200];
int b[200];
int c[200];
int t[200];
int dp[200][200]; // dp[day][used]
int ans;

int main() {
    scanf("%d %d", &d, &n);

    for (int i=0; i<d; i++) {
        scanf("%d", &t[i]);
    }

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

    for (int i=0; i<n; i++) {
        if (t[0] < a[i] || b[i] < t[0]) dp[0][i] = -INF;
    }

    for (int i=1; i<d; i++) {
        for (int j=0; j<n; j++) {
            if (t[i] < a[j] || b[j] < t[i]) continue;
            for (int k=0; k<n; k++) {
                int val;

                if (dp[i-1][k] < 0) continue;
                val = dp[i-1][k] + abs(c[j] - c[k]);
                dp[i][j] = max(dp[i][j], val);
            }
        }
    }

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

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