Gibonni

문제

Na spektakularnom koncertu koji je Gibonni održao u zagrebačkoj lažnoj Areni, njegov obožavatelj Marin ostao je fasciniran oblicima koji su se prikazivali na ekranima iza velikog glazbenika.

Nadahnut tim oblicima, Marin je odlučio završiti svoju programersku karijeru i postati keramičar. I to ne bilo kakav keramičar, bit će keramičar koji će koristiti isključivo pločice koje podsjećaju na oblike s Gibonnijevog koncerta.

Već je nabavio $nn$ takvih pločica, a $ii$-tu pločicu opisao je s četiri prirodna broja $t_{i}t\_i$, $w_{i}w\_i$, $h_{i}h\_i$, $p_{i}p\_i$ na sljedeći način:

• Pločica se sastoji od kvadratića: $w_{i}w\_i$ označava broj stupaca, a $h_{i}h\_i$ broj redaka kvadratića.
• Broj $t_{i}t\_i$ može biti $11$ ili $22$, a predstavlja tip pločice: pločici tipa $t_i=1t\_i\; =\; 1$ u najgornjem retku nedostaje kvadratić u pi-tom stupcu, a pločici tipa $t_i=2t\_i\; =\; 2$ u najgornjem retku nedostaju svi kvadratići osim onog u $p_{i}p\_i$-tom stupcu. Ostali retci pločice imaju sve kvadratiće.

Pločice je moguće okretati ulijevo i udesno, pa svaka pločica ima najviše četiri različita položaja.

[이미지 3]

Ilustracija svih mogućih položaja za pločicu opisanu s 1 3 4 3

Za svoj prvi keramičarski pohvat, Marin je odlučio posložiti svoje pločice u pravokutnik maksimalne moguće površine. Pritom neće nužno iskoristiti sve pločice, ali pazit će na to da među pločicama ne ostanu praznine.

Dok se on još divi svojim pločicama, pomozite mu tako što ćete odrediti površinu tog pravokutnika.

입력

U prvom retku je prirodan broj $nn$ (1 ≤ n ≤ 6), broj pločica.

Slijedi $nn$ redaka po četiri prirodna broja $t_{i}t\_i$, $w_{i}w\_i$, $h_{i}h\_i$, $p_{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), opis $ii$-te pločice.

출력

U prvi i jedini redak ispišite traženi broj.

힌트

Pojašnjenje prvog probnog primjera: Na ilustraciji su prikazane pločice kojima raspolaže (redom kao u ulaznim podacima) i jedan od načina kako postići pravokutnik površine 35. Pritom jedna pločica nije iskorištena.

[이미지 4]

Pojašnjenje drugog probnog primjera:

[이미지 5]

Pojašnjenje trećeg probnog primjera: Zadane su pločice iz teksta zadatka. Nemoguće ih je složiti u pravokutnik bez praznina.