Khu phố BBB có tổng cộng ~n~ nhà trượt băng được xây dựng trên ~n~ đồi tuyết, đồi thứ ~i~ có khoảng cách ~x_i~ km tính từ bờ biển. Tất cả nhà trượt băng đều mở cửa cùng lúc mỗi ngày, nhà trượt băng thứ ~i~ mở cửa trong vòng ~t_i~ phút. Bản đồ khu phố có thể xem như trục tọa độ nằm ngang.

CCC đến thăm khu phố trong ~m~ ngày và muốn trải nghiệm trượt băng mỗi ngày. Vào ngày thứ ~i~, CCC xuất phát từ địa điểm cách bờ biển ~a_i~ km, thời điểm xuất phát trùng với thời điểm mở cửa của các nhà trượt băng. CCC di chuyển được quãng đường ~1~ km mỗi phút và có thể di chuyển sang phải hoặc sang trái. Nếu vị trí hiện tại của CCC có đồi tuyết, CCC có thể leo lên đồi, tham gia trượt băng hoặc có thể bỏ qua đồi tuyết và tiếp tục di chuyển.

Thời gian leo lên đồi tuyết xem như không đáng kể và CCC tham gia trượt băng cho đến khi nhà trượt băng tại vị trí đó đóng cửa. Sau đó, CCC phải leo xuống đồi tuyết, đồi tuyết thứ ~i~ mất ~s_i~ phút để leo xuống. Sau khi leo xuống, CCC có thể tiếp tục di chuyển sang phải hoặc sang trái như thường.

Hình minh họa cho ví dụ đầu tiên. CCC xuất phát tại vị trí ~1~. CCC mất ~2~ phút để đến đồi tuyết tại vị trí ~3~, leo lên đồi và trượt băng trong vòng ~5~ phút, sau đó leo xuống đồi trong vòng ~0~ phút. Sau đó, CCC tiếp tục di chuyển đến vị trí ~6~ trong vòng ~3~ phút, leo lên đồi và trượt băng trong vòng ~1~ phút. Tổng thời gian trượt băng của CCC trong ngày là ~5+1=6~ phút.

CCC muốn biết tổng lượng thời gian trượt tuyết tối đa trong mỗi ngày. Lưu ý rằng nếu tại vị trí xuất phát trùng vị trí của đồi tuyết thì CCC phải leo lên đồi trước khi đến nhà trượt băng.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \le n,m \le 10^5)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~x_i, \; t_i~ và ~s_i~ ~(0 \le x_i,t_i,s_i \le 10^9)~.
• Dòng cuối cùng chứa ~m~ số nguyên ~a_i~ ~(0 \le a_i \le 10^9)~.

Output

• In ra trên một dòng gồm ~m~ số nguyên, số nguyên thứ ~i~ là tổng lượng thời gian trượt tuyết tối đa trong ngày ~i~.

Samples

Samples Input 1

3 1
3 7 0
6 11 3
10 13 5
1

Samples Output 1

6

Samples Input 2

3 2
5 10 3
3 6 1
1 5 0
0 3

Samples Output 2

5 8

Samples Input 3

1 3
3 3 3
0 1 2

Samples Output 3

0 1 2

Scoring

• Subtask ~1~ với ~21\%~ số điểm: ~n,m \le 10~
• Subtask ~2~ với ~27\%~ số điểm: ~m=1; \; a_1=0~
• Subtask ~3~ với ~31\%~ số điểm: ~n,m \le 1000~
• Subtask ~4~ với ~21\%~ số điểm: Không có ràng buộc gì thêm