Vrsar là một thị trấn nhỏ ven biển gồm ~n~ quả đồi. Điều đáng ngạc nhiên là khi nhìn từ biển, các quả đồi xếp thành một hàng nối tiếp nhau sao cho quả đồi thứ ~i~ cách biển ~x_i~ mét. Trên đỉnh mỗi quả đồi có một sân trượt băng. Tất cả các sân trượt băng mở cửa cùng lúc, nhưng không đóng cửa cùng lúc: sân thứ ~i~ mở trong ~t_i~ phút.

Iva và Mia đến Vrsar và sẽ ở đây ~m~ ngày. Hai bạn rất thích trượt băng và muốn trượt băng mỗi ngày. Vào đầu ngày thứ ~i~, hai bạn ở vị trí cách biển ~a_i~ mét, và cuộc phiêu lưu trượt băng bắt đầu đúng lúc các sân trượt mở cửa. Để tới một sân trượt, hai bạn phải đi bộ tới đó với tốc độ một mét mỗi phút. Hai bạn có thể đi cả sang trái và sang phải. Nếu đang ở vị trí có một quả đồi, hai bạn có thể leo lên và tới sân trượt trên đỉnh, hoặc đi qua nó mà không leo.

Hai bạn có thể lực rất tốt nên leo đồi không mất thêm thời gian. Khi đã lên tới đỉnh, hai bạn có thể trượt băng bao lâu tùy ý cho tới khi sân trượt đóng cửa. Đi xuống thì không dễ như đi lên: trời vừa mưa nên mặt đất trơn, việc xuống quả đồi thứ ~i~ mất ~s_i~ phút. Sau khi xuống khỏi một quả đồi, hai bạn có thể tiếp tục đi bộ tới sân trượt tiếp theo.

Iva và Mia muốn biết số phút trượt băng nhiều nhất mà hai bạn có thể đạt được mỗi ngày. Trong một ngày, hai bạn có thể ghé bao nhiêu sân trượt cũng được. Hãy giúp hai bạn nhé!

Lưu ý: Nếu đầu ngày Iva và Mia ở đúng vị trí của một quả đồi thì hai bạn đang ở chân đồi, nên vẫn phải leo lên nếu muốn trượt băng trên đỉnh.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ — số quả đồi và số ngày.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~x_i~, ~t_i~ và ~s_i~ — khoảng cách của quả đồi thứ ~i~ tới bờ biển, thời điểm đóng cửa của sân trượt, và thời gian cần để xuống khỏi quả đồi đó.
• Dòng cuối chứa ~m~ số nguyên ~a_i~ — khoảng cách của Iva và Mia tới bờ biển vào đầu ngày thứ ~i~.

Kết quả

In ra trên một dòng gồm ~m~ số nguyên, số thứ ~i~ là thời gian trượt băng nhiều nhất mà Iva và Mia đạt được trong ngày thứ ~i~.

Ví dụ

Đầu vào:

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

Đầu ra:

6

Giải thích: Hai bạn ở vị trí ~1~. Đi bộ ~2~ phút tới sân trượt trên quả đồi ở vị trí ~3~ và trượt băng ở đó ~5~ phút. Sau đó xuống đồi (mất ~0~ phút), đi bộ tiếp ~3~ phút tới sân trượt trên quả đồi ở vị trí ~6~ và trượt ở đó ~1~ phút. Tổng cộng hai bạn trượt băng được ~5 + 1 = 6~ phút.

Giới hạn

• ~1 \le n, m \le 10^5~
• ~0 \le x_i, t_i, s_i \le 10^9~
• ~0 \le a_i \le 10^9~