Description

Xiaohua bought a very interesting magic glasses case. The lid of the case is made of two halves, and each half is horizontally divided into several paper strips, as shown in Figure 1 (the left half is the bottom part of the case, and the right half is the top part). Gray indicates the surface of the case, and white indicates blank areas. The case in the figure has $3$ strips, and each strip has length $50$ mm, but other cases may have a different number of strips, and the lengths of the strips may also be different.

The special thing about this case is that it can be folded in two ways. Figure 1(a) and (b) show these two folding methods. The first folding method exposes areas $1,2,3$ on the surface of the case, while the second folding method exposes areas $4,5,6$ on the surface. If a case has $n$ strips, then folding method 1 exposes areas numbered $1,2,\ldots,n$, and folding method 2 exposes areas numbered $n+1,n+2,\ldots,2n$. Area $i$ and area $n+i$ are congruent. In this problem, you do not need to know how the two folding methods are converted into each other.

Xiaohua has two kinds of square paper pieces: formula pieces and cartoon pictures. She wants to stick the formula pieces onto areas $1,2,3$, and stick the cartoon pictures onto areas $4,5,6$, so that she can use folding method 1 when studying and folding method 2 when resting. Each paper piece must lie completely inside an area, and its boundary is allowed to coincide with the boundary of the area. Different paper pieces must be placed in different areas, and some areas may also be left empty.

A standard case has length $150$, width $55$, and area $8250$. It is divided into three strips of equal length, so each white area has size $55 \times 50$. Xiaohua has $3$ formula pieces with side lengths $40,45,52$, and $4$ cartoon pieces with side lengths $10, 27, 30, 55$. She can only place $40$ and $45$ on the front side, and $10,27,30$ on the back side. Obviously, the standard case cannot meet her needs.

Fortunately, the case company allows users to customize their own cases: the case length, width, number of strips, and the length of each strip can all be modified arbitrarily. That is, the length does not have to be $150$, and the width does not have to be $55$. Xiaohua found that if the case size stays the same, but the strips are changed to four strips with lengths $40,45,55,10$, then all pieces can fit, as shown in Figure 2.

A larger-area case is more expensive, so Xiaohua wants to buy a case with area not exceeding $s$. How should she choose the case, design the strips, and place the small paper pieces, so that the total number of pieces on the case is as large as possible? Under the condition that the number of pieces is maximized, what is the minimum possible area of the case?

Input Format

The first line of the input contains three integers $n,m,s$, representing the numbers of formula pieces, cartoon pieces, and the upper limit on the case area, respectively. The second line contains $n$ positive integers, representing the side length of each formula piece. The third line contains $m$ positive integers, representing the side length of each cartoon picture.

Output Format

The output contains only one line with two integers $C_{max}$ and $S_{min}$, representing the maximum number of pieces that can be stuck onto the case, and the minimum case area under this condition.

3 4 10000
40 45 52
10 27 30 55

7 8250

Hint

Constraints: $1 \le n,m \le 5 \times 10^4$, $1 \le s \le 10^{13}$. All paper piece side lengths do not exceed $4 \times 10^4$.

For $50\%$ of the testdata: $1 \le n,m \le 10^3$.

Translated by ChatGPT 5