Vào thời điểm Nhật Bản đang là mùa đông, nước Úc ở Nam bán cầu lại trải qua những ngày nóng bức. IOI sống ở Úc và quyết định lên kế hoạch chọn quần áo dựa trên dự báo thời tiết cho \(D\) ngày. Nhiệt độ cao nhất của ngày thứ \(i\) (\(1\le i\le D\)) được dự báo là \(T_i\) độ.

IOI có \(N\) bộ quần áo, được đánh số từ \(1\) đến \(N\). Bộ thứ \(j\) (\(1\le j\le N\)) phù hợp để mặc vào những ngày có nhiệt độ cao nhất từ \(A_j\) đến \(B_j\) độ, kể cả hai đầu mút. Mỗi bộ quần áo còn có một số nguyên gọi là độ sặc sỡ; độ sặc sỡ của bộ thứ \(j\) là \(C_j\).

Với mỗi ngày trong \(D\) ngày, IOI chọn một bộ quần áo phù hợp với nhiệt độ cao nhất theo dự báo. Có thể chọn cùng một bộ nhiều lần, và cũng có thể có những bộ không được chọn lần nào trong \(D\) ngày.

IOI muốn hạn chế mặc những bộ quần áo giống nhau trong hai ngày liên tiếp, nên cậu muốn tổng giá trị tuyệt đối của hiệu độ sặc sỡ giữa các bộ quần áo mặc trong hai ngày liên tiếp lớn nhất có thể. Cụ thể, nếu chọn bộ \(x_i\) vào ngày thứ \(i\), cậu muốn tối đa hóa giá trị

Hãy viết chương trình tìm giá trị lớn nhất này.

Yêu cầu

Tính giá trị lớn nhất của tổng chênh lệch độ sặc sỡ giữa quần áo được chọn trong các ngày liên tiếp.

Dữ liệu vào

Dữ liệu vào gồm \(1+D+N\) dòng.

• Dòng đầu tiên chứa hai số nguyên \(D,N\) (\(2\le D\le200\), \(1\le N\le200\)), cách nhau bởi dấu cách. \(D\) là số ngày cần lên kế hoạch và \(N\) là số bộ quần áo IOI có.
• Dòng thứ \(i\) trong \(D\) dòng tiếp theo (\(1\le i\le D\)) chứa số nguyên \(T_i\) (\(0\le T_i\le60\)), cho biết nhiệt độ cao nhất dự báo cho ngày thứ \(i\) là \(T_i\) độ.
• Dòng thứ \(j\) trong \(N\) dòng tiếp theo (\(1\le j\le N\)) chứa ba số nguyên \(A_j,B_j,C_j\) (\(0\le A_j\le B_j\le60\), \(0\le C_j\le100\)). Bộ quần áo thứ \(j\) phù hợp với ngày có nhiệt độ cao nhất từ \(A_j\) đến \(B_j\) độ và có độ sặc sỡ \(C_j\).

Dữ liệu bảo đảm mỗi ngày trong \(D\) ngày đều có ít nhất một bộ quần áo phù hợp với nhiệt độ cao nhất theo dự báo.

Dữ liệu ra

In ra một dòng chứa giá trị lớn nhất của tổng giá trị tuyệt đối của hiệu độ sặc sỡ giữa các bộ quần áo mặc trong hai ngày liên tiếp, tức là giá trị lớn nhất của

3 4
31
27
35
20 25 30
23 29 90
21 35 60
28 33 40

80

Ngày thứ nhất có thể chọn bộ \(3\) hoặc \(4\); ngày thứ hai có thể chọn bộ \(2\) hoặc \(3\); ngày thứ ba chỉ có thể chọn bộ \(3\).

Chọn bộ \(4\) vào ngày thứ nhất, bộ \(2\) vào ngày thứ hai và bộ \(3\) vào ngày thứ ba, tức là \(x_1=4\), \(x_2=2\), \(x_3=3\). Giá trị tuyệt đối của hiệu độ sặc sỡ giữa hai ngày đầu là \(|40-90|=50\), còn giữa ngày thứ hai và thứ ba là \(|90-60|=30\). Tổng bằng \(80\), là giá trị lớn nhất.

5 2
26
28
32
29
34
30 35 0
25 30 100

300

Trong các ngày từ thứ nhất đến thứ năm, IOI bắt buộc phải lần lượt chọn các bộ \(2,2,1,2,1\). Giá trị cần tìm là