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

Iva và Mia đã đến Vrsar và sẽ ở đây trong vài ngày. Iva và Mia thích trượt băng và muốn trượt băng mỗi ngày khi họ ở thị trấn này. Vào đầu ngày thứ ~i~, họ cách biển ~a_i~ mét và cuộc phiêu lưu trượt băng của họ bắt đầu cùng lúc với thời điểm sân băng mở cửa. Để đến được sân trượt băng, họ phải đi bộ tới đó, di chuyển với tốc độ một mét mỗi phút. Họ có thể đi cả bên trái và bên phải. Nếu ở vị trí có đồi, họ có thể leo lên đồi và đến sân trượt băng trên đỉnh đồi, hoặc có thể đi vòng qua mà không cần leo.

Họ có thể trạng rất tốt nên có thể leo đồi mà không tốn thêm thời gian. Sau khi lên đến đỉnh, họ có thể trượt bao nhiêu tùy thích hoặc cho đến khi sân băng đóng cửa. Xuống dốc không dễ như đi lên. Gần đây trời mưa, mặt đất trơn trượt nên họ phải mất ~s_i~ phút mới xuống được ngọn đồi thứ ~i~. Sau khi xuống từ một ngọn đồi, họ có thể tiếp tục đi bộ về phía sân trượt băng tiếp theo.

Hình trên minh họa cho ví dụ đầu tiên. Iva và Mia xuất phát ở vị trí số ~1~. Họ đi bộ ~2~ phút đến sân trượt băng trên đồi ở vị trí số ~3~ và trượt băng ở đó trong ~5~ phút. Sau đó họ xuống đồi (trong ~0~ phút), tiếp tục đi bộ ~3~ phút đến sân trượt băng trên đồi ở vị trí số ~6~ và trượt băng ở đó trong ~1~ phút. Tổng cộng, họ đã trượt băng trong ~5 + 1 = 6~ phút.

Iva và Mia quan tâm đến việc xác định số phút tối đa họ có thể trượt băng mỗi ngày. Trong một ngày, họ có thể tham quan bất kỳ sân trượt băng nào. Vì họ muốn dành nhiều thời gian hơn để trượt băng và ít thời gian tính toán hơn nên họ đã nhờ bạn giúp đỡ. Hãy giúp họ giải quyết vấn đề này!

Lưu ý: Nếu Iva và Mia lúc đầu ngày ở vị trí giống như một ngọn đồi thì họ đang ở dưới chân đồi và do đó họ phải leo lên đó nếu muốn trượt băng trên sân băng trên đỉnh đồi.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \leq n, m \leq 10^5~) là số ngọn đồi và số ngày.
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa các số nguyên ~x_i~, ~t_i~ và ~s_i~ (~0 \leq x_i, t_i, s_i \leq 10^9~) là khoảng cách từ ngọn đồi thứ ~i~ đến bờ biển, thời gian đóng cửa sân băng và thời gian để xuống đồi.
• Dòng tiếp theo gồm ~m~ số nguyên ~a_i~ (~0 \leq a_i \leq 10^9~), là khoảng cách từ bờ biển ban đầu trong ngày thứ ~i~.

Output

Trong một dòng, đưa ra ~m~ số nguyên, số thứ ~i~ là thời gian lớn nhất mà Iva và Mia có thể trượt băng trong ngày thứ ~i~.

Scoring

1. ~n, m \leq 10~ (8 điểm)

2. ~m = 1, a_1 = 0~ (17 điểm)

3. ~n, m \leq 10^3~ (19 điểm)

4. Không có ràng buộc gì thêm (26 điểm)

Sample Input 1

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

Sample Output 1

6

Sample Input 2

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

Sample Output 2

5 8

Sample Input 3

1 3
3 3 3
0 1 2

Sample Output 3

0 1 2