Gibonni

화려한 콘서트에서 Gibonni가 자그레브의 이른바 '가짜 아레나'에서 공연했다. 그의 팬 Marin은 무대 뒤 화면에 나타난 도형들에 매료되었다.

그 도형에서 영감을 받은 Marin은 프로그래머 경력을 접고 도예가가 되기로 했다. 그는 Gibonni 콘서트에서 본 도형을 닮은 타일만 쓰는 도예가가 되려 한다.

그는 이미 이런 타일을 $n$개 준비했다. $i$번째 타일은 네 개의 자연수 $t_i$, $w_i$, $h_i$, $p_i$로 다음과 같이 설명된다.

• 타일은 정사각형 칸으로 이루어져 있다. $w_i$는 열의 수, $h_i$는 행의 수다.
• $t_i$는 1 또는 2이며 타일의 종류를 나타낸다. $t_i = 1$인 타일은 맨 윗줄의 $p_i$번째 열 칸이 없다. $t_i = 2$인 타일은 맨 윗줄에서 $p_i$번째 열 칸만 남고 나머지 칸이 모두 없다. 나머지 줄은 칸이 모두 있다.

1 3 4 3	2 3 4 3

타일은 왼쪽과 오른쪽으로 돌릴 수 있어서 각 타일은 최대 네 가지 방향을 가질 수 있다.

1 3 4 3으로 설명되는 타일이 가질 수 있는 모든 방향을 나타낸 그림

Marin은 타일을 넓이가 최대인 직사각형으로 배열하려 한다. 모든 타일을 쓸 필요는 없지만 타일 사이에 빈틈이 있어서는 안 된다. 그 직사각형의 넓이를 구하라.

첫 줄에 타일의 개수를 나타내는 자연수 $n$($1 ≤ n ≤ 6$)이 주어진다.

이어서 $n$개의 줄에 각각 네 개의 자연수 $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$)가 주어지며, 이는 $i$번째 타일을 나타낸다.

구한 넓이를 한 줄에 출력한다.

첫 번째 테스트 설명: 그림은 입력 순서대로 주어진 타일과 넓이 35인 직사각형을 만드는 한 가지 방법을 보여준다. 타일 하나는 사용하지 않았다.

두 번째 테스트 설명:

세 번째 테스트 설명: 문제에서 주어진 타일은 빈틈없이 직사각형으로 배열할 수 없다.