Problem: Greed

Want to try solving this problem? You can submit your code online if you log in or register.

Greed

Input File: standard input
Output File: standard output
Time Limit: 3.5 seconds
Memory Limit: 256 MB

Happy birthday! It is time to cut your cake! Including you, there are K+1 hungry people who are eager for some of your R row by C column rectangular cake. To ensure fairness, there are some rules about how you may cut your cake.

You must make K cuts, in order to split the cake into K+1 pieces.
Every cut must be made parallel to the sides of the rectangle.
Every cut must begin on either the left or bottom side of the cake, and must continue until it hits either the opposite side of the cake or an existing cut.
There are H allowed locations for horizontal cuts and V locations allowed for vertical cuts.
Once all cuts have been made, you will receive the largest piece of cake.

You love cake, but do not wish to be seen to be greedy. In order to avoid this fate, you must make the area of the largest piece of cake as small as possible.

Input

The first line of input contains five integers R,C,K,H,V.
The following H lines contain one integer each, the i-th of which being y_i. This indicates a horizontal cut can be made y_i units up from the bottom side of the cake. These will be distinct and strictly increasing.
The following V lines contain one integer each, the i-th of which being x_i. This indicates a vertical cut can be made x_i units to the right of the left side of the cake. These will be distinct and strictly increasing.

Output

Output must consist of a single integer representing the area of the smallest possible largest slice of cake.

Sample Input

Sample Output

Explanation

In this example, it is possible for us to create vertical cuts at 2, 5, and 6, as well as horizontal cuts at 3 and 5.

By first cutting the cake vertically at position 5, and then horizontally at position 3, we can produce two slices of area 15 and once slice of area 18. This is the smallest we can make the largest slice, and so we output 18.

Subtasks & Constraints

For all subtasks, 1 ≤ K ≤ H + V, 0 ≤ H, V ≤ 1500, 2 ≤ R, C, 4 ≤ RC ≤ 2³⁰, 1 ≤ x_i < C and 1 ≤ y_i < R.

For Subtask 1 (10 points), H, V ≤ 10.
For Subtask 2 (15 points), K = H + V ≤ 40.
For Subtask 3 (15 points), H, V ≤ 40.
For Subtask 4 (20 points), H, V ≤ 100.
For Subtask 5 (20 points), K ≤ 100, H, V ≤ 300.
For Subtask 6 (20 points), no additional constraints.