Khuyến khích các bạn giải bài Mua đất trước khi làm bài này.

Cho hai dãy ~a, b~ lần lượt có độ dài ~n, m~.

Gọi ~c~ là bảng có kích thước ~n \times m~, trong đó ~c_{ij} = a_i \times b_j~ ~(c_{ij}~ có nghĩa là ô vuông ở hàng thứ ~i~, cột thứ ~j~ của bảng ~c)~.

Hãy tìm hình chữ nhật con có diện tích lớn nhất sao cho tổng các phần tử của nó không vượt quá ~x~. Nói cách khác, hãy tìm số nguyên ~S~ lớn nhất thoả mãn tồn tại ~4~ số nguyên dương ~x_1, y_1, x_2, y_2~ thoả mãn ~1 \le x_1 \le x_2 \le n; \ 1 \le y_1 \le y_2 \le m; \ (x_2 - x_1 + 1) \times (y_2 - y_1 + 1) = S,~ và: $$\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2}C_{ij} \le x.$$

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n, m, x \ (1 \le x \le 2 \times 10^9);~
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n \ (1 \le a_i \le 1000; \ 1 \le i \le n);~
• Dòng thứ ba gồm ~m~ số nguyên ~b_1, b_2, ..., b_n \ (1 \le b_i \le 1000; \ 1 \le i \le m).~

Output

Một số nguyên là kết quả của bài toán. Nếu không có hình chữ nhật con nào thoả mãn thì in ra ~0~.

Subtasks

• Subtask 1 [20%]: ~1 \le n, m \le 50;~
• Subtask 2 [40%]: ~1 \le n, m \le 500;~
• Subtask 3 [40%]: ~1 \le n, m \le 5000.~

Examples

Input

3 3 9
1 2 3
1 2 3

Output

4

Giải thích

Input

5 1 5
5 4 3 4 5
2

Output

0

Giải thích