JOI có \(N\) thành phố đánh số \(1\) đến \(N\) và \(N-1\) tuyến đường sắt; tuyến \(i\) nối hai chiều thành phố \(i\) và \(i+1\). Đi tuyến \(i\) bằng vé giấy tốn \(A_i\) yên. Đi bằng thẻ IC tốn \(B_i\) yên mỗi lượt, nhưng trước đó phải mua riêng thẻ của tuyến ấy với giá \(C_i\); thẻ dùng được không giới hạn và không dùng được cho tuyến khác. Luôn có \(A_i>B_i\).

Bạn lần lượt ghé \(P_1,P_2,\ldots,P_M\), đi từ \(P_j\) tới \(P_{j+1}\) trong ngày \(j\). Ban đầu bạn không có thẻ. Hãy chọn trước các thẻ cần mua và cách trả tiền để tổng giá thẻ cùng tiền tàu nhỏ nhất.

Dữ liệu vào

• Dòng 1: \(N,M\).
• Dòng 2: \(P_1,\ldots,P_M\).
• \(N-1\) dòng tiếp: \(A_i,B_i,C_i\).

Dữ liệu ra

In chi phí nhỏ nhất, theo yên.

Ràng buộc

• \(2\le N,M\le100\,000\),
• \(1\le B_i<A_i\le100\,000,\quad1\le C_i\le100\,000\),
• \(1\le P_j\le N,\quad P_j\ne P_{j+1}\).

Phân nhóm

• Nhóm 1 (20 điểm): \(N\le1000\), \(M=2\), \(A_i,B_i,C_i\le1000\).
• Nhóm 2 (30 điểm): \(N,M\le1000\), \(A_i,B_i,C_i\le1000\).
• Nhóm 3 (50 điểm): không có ràng buộc bổ sung.

Ví dụ

4 4
1 3 2 4
120 90 100
110 50 80
250 70 130

550

8 5
7 5 3 5 4
12 5 8
16 2 1
3 1 5
17 12 17
19 7 5
12 2 19
4 1 3

81