Nikola là một người đam mê sưu tập album với hình ảnh các cầu thủ bóng đá. Anh và bạn bè của mình cạnh tranh với nhau trong một trò chơi họ tự phát minh dựa trên các album hiện đang được sưu tập. Những hình ảnh trong album đó được chia thành ~N~ đội, mỗi đội có chính xác ~M~ cầu thủ bóng đá. Quy tắc chính của trò chơi là tổng số điểm mà một người thắng cho đội thứ ~i~ là ~B_x~, trong đó ~x~ là tổng số hình ảnh độc đáo của các cầu thủ bóng đá của đội đó mà người đó đã thu thập được. Họ cũng đã đồng ý rằng mảng ~B~ là tăng dần, tức là có nhiều hình ảnh độc đáo của các cầu thủ bóng đá trong một đội nghĩa là có nhiều hoặc bằng điểm số hơn.

Nikola muốn giành được nhiều điểm nhất có thể trong trò chơi. Đối với mỗi đội ~x~, số lượng hình ảnh độc đáo hiện tại mà Nikola sở hữu của đội đó, ~P_x~, được biết đến.

Ivan là một người bạn của Nikola, người đã sưu tập toàn bộ album hai lần và khi nghe về trò chơi mà Nikola chơi với bạn bè của mình, anh ta quyết định tặng cho Nikola bất kỳ ~K~ hình ảnh nào mà Nikola muốn. Sau khi biết được tin vui này, Nikola tự hỏi số điểm tối đa mà anh ta có thể đạt được sau khi Ivan tặng cho anh ta ~K~ hình ảnh. Quá phấn khởi trước tin tức này, anh ấy không thể tính toán và nhờ bạn trả lời câu hỏi của mình.

Input

• Dòng đầu tiên có các số nguyên ~N, M~ và ~K~ ~(1 \leq N, M \leq 500, 1 \leq K \leq min(N \times M, 500))~, các số từ đề bài.
• Dòng thứ hai có một mảng ~P~ gồm ~N~ số nguyên không âm ~(0 \leq P_i \leq M)~.
• Dòng thứ ba có một mảng ~B~ gồm ~M+1~ số nguyên không âm ~(0 \leq B_i \leq 100000)~, số điểm Nikola nhận được cho ~i~ ~(0 \leq i \leq M)~ hình ảnh độc đáo của một đội.

Với mọi ~t~ từ ~0~ đến ~M-1~, ~B_t \leq B_{t+1}~. Cũng đảm bảo rằng ~K \leq N \times M - (P_1 + P_2 + … + P_N)~.

Output

Trong dòng duy nhất in ra câu trả lời cho câu hỏi của Nikola.

Chú thích

• ~20 \%~ điểm, ~K~ sẽ là ~2~.

Sample Input 1

4 4 3
4 2 3 1
0 1 3 6 10

Sample Output 1

31

Sample Input 2

4 3 5
1 1 2 3
0 1 2 3

Sample Output 2

12

Sample Input 3

3 6 2
2 4 1
31 38 48 60 75 91 120

Sample Output 3

206

Giải thích

Trong test đầu tiên, Nikola có khả năng cao sẽ yêu cầu Ivan tặng cho anh một hình ảnh của đội thứ ba và hai hình ảnh từ đội thứ hai, để điểm số của anh là ~31 \times (10 + 10 + 10 + 1)~.