Trò chơi ở đây là một đường đu gồm ba dải ô song song mỗi dải có \(n + 2\) ô, đều được đánh số từ 0 (ở đầu trái) đến \(n + 1\) (ở đầu phải).

Ví dụ, xét hình dưới đây, với \(n = 6\)

Ví trí xuất phát	3	-4	-5	5	10	3	Vị trí kết thúc
	6	2	-3	-3	1	-1
	-2	13	1	0	7	4

Các ô từ 1 đến \(n\) của mỗi dải đều có ghi một số nguyê. Mỗi người chơi xuất phát từ ô ở cột 0, liên tục tiến về phóa trước bằng cách nhảy lò cò (nhảy bằng một chân) theo quy tắc sau đây:

+ Nếu đang đứng ở một ô ở dải giữa thì bước tiếp theo sẽ nhảy về phía trước vào một trong hai ô ở dải hai bên.

+ Nếu đang đứng ở một ô không phải dải giữa thì bước tiếp theo sẽ nhảy về phía trước vào một ô ở dải giữa.

+ Lúc ban đầu đang đứng ở vị trí xuất phát thì có thể nhảy vào ô ở dải nào cũng được.

Lượt chơi kết thúc khi người chơi nhảy vào ô ở cột \(n + 1\) là ô cuối cùng của đường đua.

Ngoài ra, nếu đang đứng ở ô \(i\ (i = 0,1,\ldots,n)\) thì trong bước tiếp theo, chỉ có thể nhày vào ô \(j\) sao cho \(i + 1 \leq j \leq i + p\), trong đó \(p\) là một số nguyên dương cho trước không lớn hơn \(n\) (đương nhiên phải có \(j \leq n + 1)\). \(p\) được gọi là độ dài tối đa của bước nhảy.

Điểm số mà người chơi giành được sau lượt chơi chính là tổng của tất cả các số thuộc các ô mà người chơi đã nhảy vào đó.

Yêu cầu: Xác định điểm số tối đa mà một người chơi có thể đạt được.

Dữ liệu vào:

+ Dòng đầu tiên ghi hai số nguyên \(n,\ p\ (2 \leq n \leq 10^{5},1 \leq p \leq \min(50,n))\);

+ Dòng thứ hai ghi \(n\) số nguyên, lần lượt là các số ghi trên các ô từ đầu trái của dải ô thứ nhất.

+ Dòng thứ ba ghi \(n\) số nguyên, lần lượt là các số ghi trên các ô từ đầu trái của dải ô thứ hai (dải ở giữa)

+ Dòng thứ tư ghi \(n\) số nguyên, lần lượt là các số ghi trên các ô từ đầu trái của dải ô thứ ba.

Tất cả các số ghi trên các ô nói trên đều có giá trị tuyệt đối không vượt quá 10000.

Kết quả:

+ Ghi một số nguyên là số điểm tối đa đạt được.

Ví dụ:

Input	Output
6 3 3 -4 -5 5 10 2 6 2 -3 -2 1 -1 -2 13 1 0 7 4	27

Ràng buộc:

+ Có 30% số test tương ứng 30% số điểm có \(1 \leq m,n \leq 100;k = 0;q \leq 10^{2}\);

+ Có 20% số test khác tương ứng 20% số điểm có \(1 \leq m,n \leq 100;0 < k \leq 10;q \leq 10^{2}\);

+ Có 50% số test còn lại tương ứng 50% số điểm không có ràng buộc gì thêm.

Giải thích: Lần lượt thực hiện:

Nhả vào ô ở giữa cột 1 (nhận được 6 điểm)

Nhảy vào ô bên phải (dải thứ ba) ở cột 2 (nhận thêm 13 điểm)

Nhảy vào ô giữa ở cột 4 (nhận thêm -2 điểm)

Nhảy vào ô bên trái (dải thứ nhất) ở cột 5 (nhận thêm 10 điểm)

Nhày vào ô giữa ở cột 7 và kết thúc lượt chơi, nhận được tổng cộng 27 điểm.

Ràng buộc:

+ 30% số test tương ứng với 30% số điểm có \(1 \leq n \leq 20\) và \(p = 4\);

+ 20% số test tương khác ứng với 20% số điểm có \(20 \leq n \leq 50\);

+ 50% số test tương còn lại ứng với 50% số điểm không có ràng buộc gì thêm;