Hide

Problem B
Äta choklad

Languages en sv

Olle och Lisa har fått $N$ typer av chokladkakor i olika former av sina föräldrar, som de nu planerar att äta tillsammans (chokladkakorna, inte föräldrarna). Varje chokladkaka är en rektangel som består av $R_{i} \times C_{i}$ rutor. De har fått $k_{i}$ kopior av typ $i$ . Chokladkakorna ligger på ett bord, och för att äta upp dem kommer de turas om att göra följande drag:

Välja en chokladkaka från bordet.
Bryta den i två delar, så att båda delarna är rektanglar med sidor av heltalslängd.
Äta upp den mindre delen.
Lägga tillbaka den andra delen på bordet igen.

Om chokladkakan de väljer har storlek $1 \times 1$ äter de upp den direkt, och lägger inte någonting på bordet. De har redan bestämt att Lisa får börja.

På grund av syskonkärlek kommer de alltid att välja en chokladkaka från bordet som, efter att de delat den i två och lagt tillbaka den större biten, innebär att de själva äter så mycket som möjligt i det draget. Om det finns flera sådana val väljer de godtyckligt bland dem. Olle är dessutom väldigt mån om rättvisa, och vill gärna att de totala antalen rutor choklad de båda äter ska vara så lika som möjligt. För att uppnå detta mål kan han innan de börjar välja att slänga högst en chokladkaka i soptunnan utan att Lisa märker någonting.

Låt $V_{O}$ och $V_{L}$ vara antalet rutor Olle respektive Lisa äter, givet att de båda äter på ett glupskt sätt. Din uppgift är att bestämma vad den minimala skillnaden, alltså $| V_{O} - V_{L} |$ , är, efter att Olle slängt högst en chokladkaka.

Indata

På den första raden står talet $N$ ( $1 \leq N \leq 10^{5}$ ), antalet chokladkakor på bordet. Därefter följer $N$ rader, där den $i$ :te raden har talen $R_{i}$ , $C_{i}$ och $k_{i}$ ( $1 \leq R_{i}, C_{i} \leq 10^{6}$ , $1 \leq k_{i} \leq 10^{9}$ ), vars betydelse beskrivits ovan.

Utdata

Skriv ut ett heltal, det minimala värdet på $| V_{O} - V_{L} |$ som beskrivet ovan.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp	Poäng	Gränser
$1$	$4$	$N = 1$
$2$	$12$	$N \leq 50, K_{i} \leq 5$
$3$	$15$	$N \leq 200, K_{i} \leq 5$
$4$	$10$	$R_{i}, C_{i} \leq 10$
$5$	$13$	$N \leq 200$
$6$	$16$	$K_{i} = 1$
$7$	$30$	Inga ytterligare begränsningar.

Förklaring av exempelfall 1

Olle slänger chokladkakan med storlek $2 \times 2$ . Därefter kommer de att två gånger vardera äta en ruta choklad, och alltså är $V_{O} = V_{L}$ .

Förklaring av exempelfall 2

I detta testfall är det optimalt för Olle att inte slänga någon chokladkaka. De kommer då att äta precis lika mycket choklad.

Sample Input 1	Sample Output 1
3 1 2 1 2 2 1 2 1 1	0

Sample Input 2	Sample Output 2
1 1 1 4	0

Sample Input 3	Sample Output 3
3 4 7 1 8 8 1 4 1 1	10

Sample Input 4	Sample Output 4
4 12 34 1 13 37 2 20 25 3 1 101 4	94

Problem BÄta choklad