Gibonni

Time limit1sMemory limit1024 MB

Summary

Given up to six tiles with a notch in the top row, find the largest rectangle area that a subset of them can tile without gaps, with rotations allowed.

Level: Medium6 of 10
Topics: Backtracking, Brute force, Matrix
Solved: No attempts yet

Problem

At a spectacular concert in Zagreb's so-called fake Arena, Gibonni had his fan Marin fascinated by the shapes shown on the screens behind the musician.

Inspired by those shapes, Marin decided to end his programming career and become a potter. He wants to be a potter who uses only tiles that resemble the shapes from Gibonni's concert.

He already has $n$ such tiles. The $i$ -th tile is described by four natural numbers $t_i$ , $w_i$ , $h_i$ , $p_i$ as follows:

The tile is made of unit squares. $w_i$ is the number of columns and $h_i$ is the number of rows.
$t_i$ is either 1 or 2 and gives the tile type. In a tile of type $t_i = 1$ , the top row is missing the square in column $p_i$ . In a tile of type $t_i = 2$ , the top row is missing every square except the one in column $p_i$ . All other rows are complete.



`1 3 4 3`	`2 3 4 3`

Tiles can be rotated left and right, so each tile has at most four different orientations.

Illustration of all possible orientations for the tile described by 1 3 4 3

Marin wants to arrange his tiles into a rectangle of the largest possible area. He does not have to use all the tiles, but there must be no gaps between them. Find the area of that rectangle.

Input

The first line contains a natural number $n$ ( $1 ≤ n ≤ 6$ ), the number of tiles.

Each of the next $n$ lines contains four natural numbers $t_i$ , $w_i$ , $h_i$ , $p_i$ ( $1 ≤ t_i ≤ 2$ , $1 ≤ w_i ≤ 4$ , $2 ≤ h_i ≤ 4$ , $2 ≤ w_i \cdot h_i ≤ 12$ , $1 ≤ p_i ≤ w_i$ ), describing the $i$ -th tile.

Output

Print one line with the requested area.

Hint

Explanation of the first test case: The illustration shows the tiles in input order and one way to form a rectangle of area 35. One tile is not used.

Explanation of the second test case:

Explanation of the third test case: The tiles from the statement cannot be arranged into a rectangle without gaps.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
3
2 4 2 3
2 3 2 2
2 3 3 1
```
Expected output
```
16
```
Example 3
Input
```
2
1 3 4 3
2 3 4 3
```
Expected output
```
0
```