Chính phủ đang triển khai ~m~ công trình trọng điểm quốc gia. Mỗi ngày công trình thứ ~i~ tiêu hết ~s_i~ triệu đồng.

Để hạn chế ảnh hưởng của suy thoái kinh tế, chính phủ quyết định tung ra ~n~ gói kích cầu, mỗi gói có giá trị ~p~ triệu đồng. Các gói kích cầu sẽ được ưu tiên chi cho các công trình trọng điểm. Gói kích cầu thứ ~j~ sẽ bắt đầu được giải ngân từ ngày ~rj~. Nếu nó được chi cho công trình ~i~ thì sau ~ti~ ngày toàn bộ tiền của gói kích cầu được sử dụng hết, trong đó ~ti~ là số nguyên nhỏ nhất không nhỏ hơn ~\displaystyle \frac{p}{si}~. Mỗi gói kích cầu được chi trọn cho một công trình nào đó. Mỗi công trình có thể nhận được nhiều gói kích cầu, nhưng phải sử dụng lần lượt hết gói này đến gói khác, trong một ngày không được rút tiền từ quá một gói kích cầu.

Các gói kích cầu phải được giải ngân hết càng sớm càng tốt. Thủ tướng chính phủ muốn các bộ phận chức năng cho biết thời hạn ngắn nhất giải ngân hết các gói kích cầu.

Ví dụ, với số công trình là ~2~, chi phí mỗi ngày cho mỗi công trình là ~2~ và ~5~ triệu đồng, có ~4~ gói kích cầu, giá trị mỗi gói ~22~ triệu, được phép giải ngân bắt đầu từ các ngày ~1~, ~3~, ~8~ và ~12~. ~17~ ngày sẽ là thời ngắn nhất giải ngân hết các gói kích cầu.

Yêu cầu: Cho các số nguyên ~m~, ~n~, ~p~, ~si~ và ~ri~ ~(1 \leq m, n \leq 100, 1 \leq p, si, ri \leq 10^9)~. Hãy xác định số ngày ít nhất cần thiết để giải ngân hết các gói kích cầu.

Dữ liệu vào

• Dòng đầu tiên chứa ~3~ số nguyên ~m~, ~n~ và ~p~.
• Dòng thứ ~2~ chứa ~m~ số nguyên ~s1, s2, \dots, s_m~.
• Dòng thứ ~3~ chứa ~n~ số nguyên ~r1, r2, \dots, r_n~.

Dữ liệu ra

• Một số nguyên là số ngày ít nhất cần thiết để giải ngân hết các gói kích cầu.

Ví dụ

Input

2 4 22
2 5
1 3 8 12

Output

17