Nhân dịp không phải đi dạy trên trường, thầy NamDVH quyết định đi du lịch tại 1 hòn đảo xa xôi hẻo lánh nhằm tránh xa những xô bồ của cuộc sống. Sau 2 ngày 2 đêm lênh đênh trên biển, cuối cùng thầy cũng đã đến nơi. Sau khi đặt chân đến nơi, thầy bắt đầu đi thăm quan hòn đảo, bỗng nhiên thầy phát hiện ra một mảnh đất kì lạ. Mảnh đất được rào dây theo hình chữ nhật, được tách ra thành ~3~ hàng và ~n~ cột. Sau khi quan sát, thầy đi tới mảnh đất này. Sau khi vào, thầy phát hiện ra khi thầy bước chân vào 1 ô thì tài khoản ngân hàng của thầy tự nhiên nhận được 1 số tiền. Hí hửng, thầy đi qua tất cả các ô, thầy phát hiện ra: khi bước vào 1 ô, tài khoản của thầy có thể nhận tiền hoặc tài khoản của thầy có thể bị trừ tiền (số tiền cộng hoặc trừ đi giữa các ô có thể khác nhau). Hơn nữa, thầy nhận thấy các ô ở hàng thứ 2 bị rào chắn không bước vào được, nhưng các ô ở hàng 1 và hàng 3 có thể đi thoải mái.

Đang suy tư, thì thầy nhận được ~q~ tin nhắn, đọc thì thầy nhận ra đó là những lời mời đặc biệt: Lời mời thứ ~i~ cho phép mở các ô ở hàng thứ hai, từ cột ~l_i~ đến cột ~r_i~, nhưng thầy phải quét mã QR và trả ~c_i~ tiền để chấp nhận lời mời đó. Thầy cũng nhận thêm 1 tin nhắn rằng: "Thầy có thể nhận bất kỳ tập lời mời nào. Nếu nhiều lời mời cùng mở một ô, thầy vẫn phải trả phí của tất cả lời mời đã nhận."

Sau khi đọc hết các tin nhắn, thầy nghĩ ra một bài toán để đố các bạn sinh viên sau khi thầy trở về từ chuyến đi: "Nếu thầy NamDVH bắt đầu tại ô ~(1,1)~ và cần đến ô ~(3,n)~. Mỗi bước, thầy chỉ có thể đi sang phải hoặc đi xuống. Tiền của tất cả các ô thầy đi qua, bao gồm ô bắt đầu và ô kết thúc, sẽ được cộng vào tài khoản của thầy. Để đến đến hàng thứ 3, thầy phải nhận 1 số lời mời đặc biệt ở mở một số ô ở hàng thứ 2, tuy nhiên tài khoản của thầy vẫn có thể nhận được tiền tương ứng nếu đi qua các ô ở hàng thứ 2. Thầy muốn tìm số tiền nhất lớn nhất thầy có thể đạt được sau khi đến ô ~(3, n)~"

Đầu vào

• Dòng đầu chứa hai số nguyên dương ~n,q~ (~1 \le n,q \le 5 \cdot 10^5~).
• Ba dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên ~a_{i,1},a_{i,2},\ldots,a_{i,n}~, mô tả số tiền được nhận của một hàng.
• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~l_i,r_i,c_i~ — mô tả lời mời thứ ~i~.

Đầu ra

In ra một số nguyên duy nhất — điểm tiền lớn nhất thầy NamDVH có thể đạt được.

Giới hạn

• ~-10^9 \le a_{i,j} \le 10^9~.
• ~1 \le l_i \le r_i \le n~.
• ~1 \le c_i \le 10^9~.

Giới hạn theo subtask

• Subtask ~1~ (~10\%~ số điểm): ~q=1~.
• Subtask ~2~ (~20\%~ số điểm): ~l_i=1~ với mọi ~1 \le i \le q~.
• Subtask ~3~ (~25\%~ số điểm): ~n,q \le 50~.
• Subtask ~4~ (~45\%~ số điểm): Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

4 3
1 0 2 -1
-3 1 9 2
3 2 4 1
1 2 5
2 3 4
1 4 14

Đầu ra

13

Giải thích

Thầy có thể nhận lời mời thứ hai, mở các ô ở hàng thứ hai từ cột ~2~ đến cột ~3~, rồi đi qua các ô ~(1,1)~, ~(1,2)~, ~(1,3)~, ~(2,3)~, ~(3,3)~, ~(3,4)~. Tổng số tiền các ô là ~17~, phí lời mời là ~4~, nên điểm cuối cùng là ~13~.