Trò chơi ở đây là một đường đua 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 trường hợp với \(n = 6\):

Các ô từ \(1\) đến \(n\) của mỗi dải đều có ghi một số nguyên. 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, … , n)\) thì trong bước tiếp theo, chỉ có thể nhảy vào ô \(j\) sao cho \(i + 1 \le j \le 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 \le 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 \le n \le 100000, 1 \le p \le 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\).

Dữ liệu ra

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

Input 1

6 3
3 -4 -5 5 10 2
6 2 -3 -2 1 -1
-2 13 1 0 7 4

Output 1

27

Giải thích:

Lần lượt thực hiện:

• Nhảy 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.

Scoring - Ràng buộc:

• 30% số test tương ứng với 30% số điểm có \(1 \le n \le 20\) và \(p = 4\);
• 20% số test khác tương ứng với 20% số điểm có \(20 \le n \le 50\);
• 50% số test còn lại tương ứng với 50% số điểm không có ràng buộc gì thêm.