AIOC Banner

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 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

Output

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

Sample Input

6 8 2 2 3
3
5
2
5
6

Sample Output

18

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 ≤ 230, 1 ≤ xi < C and 1 ≤ yi < R.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 25 May 2019, 12:23am AEST