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)
}

Python: # -*- coding: utf-8 -*-
"""
Hot days
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0579

"""
import sys


def solve(temperatures, clothes):
    points = [[] for _ in range(len(temperatures))]
    for i, t in enumerate(temperatures):
        for c in clothes:
            if c[0] <= t <= c[1]:
                points[i].append(c[-1])
        points[i].sort()

    dp = [[min(points[0]), 0], [max(points[0]), 0]]
    for p in points[1:]:
        dp = [[min(p), max(dp[0][1] + abs(min(p)-dp[0][0]), dp[1][1] + abs(min(p)-dp[1][0]))],
              [max(p), max(dp[0][1] + abs(max(p)-dp[0][0]), dp[1][1] + abs(max(p)-dp[1][0]))]]
    return max(dp[0][1], dp[1][1])


def main(args):
    d, n = map(int, input().split())
    temperatures = [int(input()) for _ in range(d)]
    clothes = [[int(x) for x in input().split()] for _ in range(n)]
    ans = solve(temperatures, clothes)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Python: def run():
  D, N = map(int, input().split())
  d_li = [int(input()) for d in range(D)]
  clothe_li = [list(map(int, input().split())) for n in range(N)]
  dp = [[0]*N for d in range(D)]
  #init
  d = d_li[0]
  for n, (a, b, c) in enumerate(clothe_li):
    if (a <= d) and (d <= b):
      dp[0][n] = 1
  #loop
  for i in range(1, D):
    d = d_li[i]
    #print(dp)
    for pre_n in range(N):
      if dp[i-1][pre_n] == 0: continue
      for n, (a, b, c) in enumerate(clothe_li):
        if (a <= d) and (d <= b):
          #print(c)
          dp[i][n] = max(dp[i][n], 
                         dp[i-1][pre_n] + abs(clothe_li[pre_n][2] - c))
  print(max(dp[-1])-1) 
    
if __name__ == '__main__':
  run()

Python: D,N=map(int,input().split())
dp=[[-1]*(N) for i in range(D+1)]
#dp[i][j][k] i日目にｊを着たときの最大
d=[]
for i in range(D):
    i=int(input())
    d.append(i)
J=[]
for j in range(N):
    a,b,c=map(int,input().split())
    J.append([a,b,c])
t=d[0]
h=[-1]*N
for j in range(N):
    a,b,c=J[j]
    if t<a or b<t:
        continue
    h[j]=c
for i in range(2,D+1):
    t=d[i-1]
    for j in range(N):
        a,b,c=J[j]
        if t<a or b<t:
            continue
        for k in range(N):
            if i==2:
                if h[k]==-1:
                    continue
                dp[i][j]=max(abs(J[k][2]-c),dp[i][j])
            if dp[i-1][k]==-1:
                continue
            dp[i][j]=max(dp[i-1][k]+abs(J[k][2]-c),dp[i][j])
ans=0
for i in range(N):
    ans=max(dp[D][i],ans)
print(ans)

Python: INF = 10 ** 20

def main():
  d, n = map(int,input().split())
  temp = [int(input()) for i in range(d)]
  temp.insert(0,0)
  
  alst = []
  blst = []
  clst = []
  
  for i in range(n):
    a,b,c = map(int,input().split())
    alst.append(a)
    blst.append(b)
    clst.append(c)
  
  dp = [[0] * n for i in range(d + 1)]
  
  t1 = temp[1]
  for i in range(n):
    if not (alst[i] <= t1 <= blst[i]):
      dp[1][i] = -INF
  
  for i in range(2, d + 1):
    t = temp[i]
    predp = dp[i - 1]

    for j in range(n):
      cj = clst[j]
      if alst[j] <= t <= blst[j]:
        save = 0
        for x in range(n):
          cx = clst[x]
          if cj >= cx:
            v = predp[x] + cj - cx
          else:
            v = predp[x] - cj + cx
          if save < v:
            save = v
        dp[i][j] = save

  print(max(dp[d]))

main()

Python: D,N = map(int,input().split())
T = [ int(input()) for i in range(D) ]
clothes = []
for _ in range(N):
  a,b,c = map(int,input().split())
  clothes.append([a,b,c])

# i日目に服jを来た時の、派手さの絶対値
dp = [ [-1]*(N) for _ in range(D+1) ]
dp[0][0] = 0

for j in range(N):
  a,b,c = clothes[j]
  if a <= T[0] <= b:
    dp[1][j] = c

for i in range(2, D+1):
  for j in range(N):
    a,b,c = clothes[j]
    if a <= T[i-1] <= b:
      for k in range(N):
        if dp[i-1][k] > -1:
          prev_c = clothes[k][2]
          if i > 2:
            dp[i][j] = max(dp[i][j], dp[i-1][k]+abs(prev_c-c))
          else:
            dp[i][j] = max(dp[i][j], abs(prev_c-c))

print(max(dp[-1]))

Python: #D
D,N = map(int,input().split())
T = [int(input()) for i in range(D)]
ABC = [list(map(int,input().split())) for i in range(N)]

can = []
for t in T:
    mini = []
    for abc in ABC:
        a,b,c = abc
        if a <= t and t <= b:
            mini.append(c)
    mini.sort()
    can.append([mini[0],mini[-1]])

dp = [[0,0] for i in range(D)]
for i in range(1,D):
    o = can[i-1]
    m = can[i]
    dp[i][0] = max(dp[i-1][0]+abs(o[0]-m[0]),dp[i-1][1]+abs(o[1]-m[0]))
    dp[i][1] = max(dp[i-1][0]+abs(o[0]-m[1]),dp[i-1][1]+abs(o[1]-m[1]))

print(max(dp[D-1]))

Python: INF = 10 ** 20
def main():
  d, n = map(int,input().split())
  temp = [int(input()) for i in range(d)]
  temp.insert(0,0)
  alst = []
  blst = []
  clst = []
  for i in range(n):
    a,b,c = map(int,input().split())
    alst.append(a)
    blst.append(b)
    clst.append(c)
  
  dp = [[0] * n for i in range(d + 1)]
  
  t1 = temp[1]
  for i in range(n):
    if not (alst[i] <= t1 <= blst[i]):
      dp[1][i] = -INF
  
  for i in range(2, d + 1):
    t = temp[i]
    predp = dp[i - 1]
    for j in range(n):
      cj = clst[j]
      if alst[j] <= t <= blst[j]:
        dp[i][j] = max(predp[x] + (cj - clst[x] if cj >= clst[x] else clst[x] - cj) for x in range(n))
  
  print(max(dp[d]))

main()

Python: D,N = map(int,input().split())

temperature = []
for _ in range(D):
	temperature.append(int(input()))
temperature.insert(0,0)
clothes = []
for _ in range(N):
	a,b,c = map(int,input().split())
	clothes.append([a,b,c])

dp = [[0]*N for i in range(D+1)]
t1 = temperature[1]
for i in range(N):
	if not (clothes[i][0] <= t1 <= clothes[i][1]):
		dp[1][i] = -10**10

for day in range(2,D+1):
	temp = temperature[day]
	pred = dp[day-1]

	for i in range(N):
		ci = clothes[i][2]
		if clothes[i][0] <= temp <= clothes[i][1]:
			max_hadesa = 0
			for j in range(N):
				cj = clothes[j][2]
				if ci >= cj:
					tmp = pred[j]+ci-cj
				else:
					tmp = pred[j]+cj-ci
				if max_hadesa<tmp:
					max_hadesa = tmp
			dp[day][i] = max_hadesa

print(max(dp[D]))

Python: INF = 10 ** 20
d, n = map(int,input().split())
temp = [int(input()) for i in range(d)]
temp.insert(0,0)
alst = []
blst = []
clst = []
for i in range(n):
  a,b,c = map(int,input().split())
  alst.append(a)
  blst.append(b)
  clst.append(c)

dp = [[0] * n for i in range(d + 1)]

for i in range(n):
  if not (alst[i] <= temp[1] <= blst[i]):
    dp[1][i] = -INF

for i in range(2, d + 1):
  t = temp[i]
  for j in range(n):
    if alst[j] <= t <= blst[j]:
      dp[i][j] = max(dp[i - 1][x] + abs(clst[j] - clst[x]) for x in range(n))

print(max(dp[d]))