Bạn có một mảng gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Vào ngày thứ ~i~ trong ~d~ ngày, bạn phải thực hiện chính xác ~1~ trong ~2~ thao tác sau đây:

• Thêm ~1~ vào ~b_i~ phần tử đầu tiên của mảng ~a~ ~(a_j = a_j + 1~ với ~1 \le j \le b_i)~

• Thêm số lượng số có giá trị bằng chính vị trí của nó ~(a_j = j)~ vào điểm của bạn và khởi tạo lại mảng ~a~ với giá trị ~0~ ~([a_1, a_2, \dots, a_n] = [0, 0, \dots, 0])~.

Điểm ban đầu của bạn là ~0~. Lưu ý rằng bạn phải thực hiện chính xác một thao tác trong hai thao tác đã nói ở trên, cũng như không thể bỏ qua ngày nào hay thực hiện cả hai thao tác cùng một ngày.

Điểm cao nhất mà bạn có thể đạt được sau ~d~ ngày là bao nhiêu?

Do ~d~ rất lớn, mảng ~b~ sẽ được nén theo dạng sau:

• Bạn được cho một mảng ~v~ gồm ~k~ phần tử: ~v_1, v_2, \dots, v_k~;

• Mảng ~b~ sẽ là: ~[v_1, v_2, \dots, v_k, v_1, v_2, \dots, v_k, \dots]~.

Input

• Dòng đầu tiên gồm ba số nguyên ~n, k, d~ ~(1 \le n, k \le 10^5, k \le d \le 10^9)~.

• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le n)~.

• Dòng thứ ba gồm ~k~ số nguyên ~v_1, v_2, \dots, v_k~ ~(1 \le v_i \le n)~.

Output

• In ra một số duy nhất là điểm tối đa bạn có thể đạt được sau ~d~ ngày.

Scoring

Sample Input 1

3 4 4
1 2 3
1 3 2 3

Sample Output 1

4

Sample Input 2

3 1 1
0 0 1
1

Sample Output 2

0

Notes

Giải thích test đề ~1~:

• Ở ngày đầu tiên, bạn chọn thao tác ~2~. Vì cả ~3~ vị trí đều thỏa mãn nên điểm hiện tại của bạn là ~3~. Dãy được khởi tạo lại về ~[0, 0, 0]~.

• Ở hai ngày tiếp theo, bạn chọn thao tác ~1~. Dãy trở thành ~[2, 2, 1]~.

• Ở ngày cuối cùng, bạn chọn thao tác ~2~. Vị trí ~2~ là vị trí duy nhất thỏa mãn và do đó điểm số được tăng thêm ~1~.

Giải thích test đề ~2~:

• Vì chỉ có ~1~ ngày, bạn chọn thao tác ~2~. Nhưng vì không có vị trí nào thỏa mãn nên đáp án là ~0~.