레이팅 미적용日本が冬であるこの時期,南半球にあるオーストラリアでは暑い日が続いている.オーストラリアに住む IOI 君は,ある D 日間の天気予報をもとに,着る服の計画を立てることにした.i 日目 (1 ≦ i ≦ D) の最高気温は T i 度であると予報されている.
IOI 君は N 種類の服を持っており,それらには 1 から N までの番号がついている.服 j (1 ≦ j ≦ N) は最高気温が A j 度以上 B j 度以下の日に着るのに適している.また,それぞれの服には「派手さ」とよばれる整数が定まっており,服 j の派手さは C j である.
D 日間のそれぞれに対し,IOI 君は,最高気温が天気予報に従ったときに着るのに適した服のうち 1 つを着る服として選ぶ.同じ服を何度選んでもよいし,D 日間で一度も選ばれない服があってもよい.
似ている服を連続して着ることをなるべく避けようと思った IOI 君は,連続する日に着る服の派手さの差の絶対値の合計をできるだけ大きくしようと考えた.すなわち,i 日目に服 x i を選んだとして,値 |C x 1 - C x 2 | + |C x 2 - C x 3 | + ... + |C x D-1 - C x D | を最大にしたい.この最大値を求めるプログラムを作成せよ.
入力は 1 + D + N 行からなる.
1 行目には,2 つの整数 D, N (2 ≦ D ≦ 200,1 ≦ N ≦ 200) が空白を区切りとして書かれている.D は服の計画を立てる日数,N は IOI 君が持っている服の種類の数を表す.
続く D 行のうちの i 行目 (1 ≦ i ≦ D) には,1 つの整数 T i (0 ≦ T i ≦ 60) が書かれている.これは,i 日目の最高気温が T i 度であると予報されていることを表す.
続く N 行のうちの j 行目 (1 ≦ j ≦ N) には,3 つの整数 A j , B j , C j (0 ≦ A j ≦ B j ≦ 60,0 ≦ C j ≦ 100) が書かれている.これらは,服 j は最高気温が A j 度以上 B j 度以下の日に着るのに適しており,派手さが C j であることを表す.
最高気温が天気予報に従ったときに着るのに適した服が,D 日間のどの日に対しても 1 つ以上存在することが保証されている.
連続する日に着る服の派手さの差の絶対値の合計,すなわち,値 |C x 1 - C x 2 | + |C x 2 - C x 3 | + ... + |C x D-1 - C x D | の最大値を 1 行で出力せよ.
3 4
31
27
35
20 25 30
23 29 90
21 35 60
28 33 4080