Thông tin

Trong sứ mệnh khám phá bản đồ số, một rô-bốt tự hành được giao nhiệm vụ di chuyển dọc theo một dãy gồm \(N\) điểm thu thập thông tin, được đánh số từ \(1\) đến \(N\).

Điểm thu thập thông tin \(i\) (\(1 \le i \le N\)) có lượng dữ liệu là \(A_i\), nếu rô-bốt thu thập thông tin tại điểm này thì sẽ tiêu thụ \(W_i\) năng lượng.

Rô-bốt được lập trình để quét các điểm thông tin liên tiếp và phải tuân thủ nghiêm ngặt các điều kiện sau:

• Số lượng điểm thu thập thông tin được quét phải là bội số của \(K\) (để đảm bảo tính toàn vẹn của các gói thông tin);

• Tổng năng lượng tiêu thụ để rô-bốt thu thập thông tin không được vượt quá giới hạn \(S\) của pin. Coi năng lượng tiêu thụ khi di chuyển qua các điểm thông tin bằng \(0\).

Yêu cầu: Hãy viết chương trình lập trình cho rô-bốt để tìm ra các điểm thông tin liên tiếp thỏa mãn điều kiện trên mà tổng lượng dữ liệu thu thập được là lớn nhất.

Input

Dữ liệu vào:

• Dòng đầu tiên gồm ba số nguyên \(N, K, S\) (\(1 \le K \le N \le 10^5\); \(1 \le S \le 10^{12}\));

• Dòng thứ hai gồm \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) (\(|A_i| \le 10^9\));

• Dòng thứ ba gồm \(N\) số nguyên \(W_1, W_2, \ldots, W_N\) (\(0 \le W_i \le 10^9\)).

Ràng buộc:

• Có \(25\%\) số test ứng với \(25\%\) số điểm thỏa mãn \(N \le 100\);

• \(25\%\) số test khác ứng với \(25\%\) số điểm thỏa mãn \(W_i = 0\) (\(1 \le i \le N\));

• \(25\%\) số test khác ứng với \(25\%\) số điểm thỏa mãn \(K = 1\);

• \(25\%\) số test còn lại ứng với \(25\%\) số điểm không có ràng buộc thêm.

Output

In ra một số nguyên là lượng dữ liệu thu thập được lớn nhất (tổng \(A_i\) lớn nhất trong các đoạn điểm liên tiếp thỏa mãn, có thể là số âm). Nếu không tồn tại các điểm thông tin liên tiếp nào khả thi, ghi ra số \(0\).

Example 1

Input:

5 2 6
3 -1 2 5 -2
2 1 2 2 1

Output:

7

Example 2

Input:

3 2 5
10 20 5
1 1 1

Output:

30

Note

Ví dụ 1: chọn hai điểm thông tin liên tiếp là \(3\) và \(4\) (có số lượng điểm là \(2\), chia hết cho \(K\)); tổng năng lượng tiêu thụ \(2 + 2 = 4 < 6\); tổng lượng dữ liệu thu thập được \(2 + 5 = 7\).

Ví dụ 2: chọn hai điểm thông tin liên tiếp là \(1\) và \(2\); tổng năng lượng tiêu thụ \(1 + 1 = 2 < 5\); tổng lượng dữ liệu thu thập được \(10 + 20 = 30\).