One Clean Slice!

Time limit1sMemory limit16 MB

Summary

Split an R by C by H block with guillotine cuts into N boxes with one raisin each to maximize the smallest box volume.

Level: Hard8 of 10
Topics: Backtracking, Binary search, Divide and conquer
Solved: No attempts yet

Problem

There is a tasty jelly. To make it easy to cut, the jelly is divided into unit cubes of volume 1: $R$ cells wide, $C$ cells deep and $H$ cells tall. The jelly holds $N$ raisins. No raisin spans more than one cell, and no cell holds two or more raisins. So the jelly can be read as a three dimensional array, and the position of a raisin is written as three integers $(r, c, h)$ . See the figure below.

Tokkaengi wants to divide the jelly into exactly $N$ pieces so that every piece holds exactly one raisin. A cut follows cell boundaries exactly, goes all the way through the piece being cut and leaves two rectangular boxes; a cut cannot stop halfway. Among the $N$ pieces, Tokkaengi wants the smallest volume to be as large as possible. Help Tokkaengi cut the jelly.

Input

The first line contains the jelly size $R$ , $C$ , $H$ and the number of raisins $N$ , separated by spaces. ( $1 \le R, C, H \le 7$ , $1 \le N \le \min(R \times C \times H, 77)$ )

Each of the next $N$ lines contains three integers $r$ , $c$ , $h$ giving the position of one raisin, separated by spaces. ( $1 \le r \le R$ , $1 \le c \le C$ , $1 \le h \le H$ ) No two raisins share a position.

Output

Print the largest volume the smallest piece can have when the jelly is divided into exactly $N$ pieces with one raisin in each piece.

Hint

This is the jelly of the example input seen from above. However well it is cut, the three pieces have volumes 2, 3 and 4.

Examples4

Example 1
Input
```
3 3 1 3
1 1 1
2 1 1
2 3 1
```
Expected output
```
2
```
Example 2
Input
```
1 1 1 1
1 1 1
```
Expected output
```
1
```
Example 3
Input
```
7 7 7 1
4 4 4
```
Expected output
```
343
```
Example 4
Input
```
7 1 1 2
1 1 1
7 1 1
```
Expected output
```
3
```