Szavazás

Péter városában választás zajlik - két párt: A és B harcol a hatalomért. A városban $N$ körzet van, körzetenként $V_i\ \ (i=1\ldots N)$ szavazóval. Egy körzet megnyerésével az adott párt $H_i\ \ (i=1\ldots N)$ helyet szerez a leendő vezető testületben. A körzetek és a választás megnyeréséhez egyszerű többség kell: amelyik párt több szvazatot kap egy körzetben az nyeri a $H_i$ helyet, amelyik párt több helyet szerez meg a vezető testületben, az nyeri a választást. Minden körzet esetén ismert az a $G_i\ \ (i=1\ldots N)$ aranytallér mennyiség, mely szükséges ahhoz, hogy egy szavazó megváltoztassa a preferenciáját. Előzetes felmérések alapján tudjuk, hogy az $i$-ik körzetben az összes $V_i=A_i + B_i$ szavazóból $A_i$ illetve $B_i$ fog az $A$-ra illetve a $B$-re szavazni. Péter azt szeretné ha az A párt nyerné meg a választást, segítsünk neki kiszámolni hogy minimálisan mennyi aranytallér kell a választás A javára billentéséhez ($M$).

Bemenet specifikáció

Az input első sorában a körzetek $N$ száma van. Az ezt követő $N$ sor az $A_i\ B_i\ H_i\ G_i\ \ (i=1\ldots N)$ számokat tartalmazza (szóközzel elválasztva).

Kimenet specifikáció

Az output egyetlen sorába az $M$ kerül.

Korlátok

$1\le N \le 100$
$1\le A_{i},\ B_{i} \le 100000$
$1\le H_{i} \le 10000$
$1\le G_{i} \le 100$
$A_{i}+B_{i}\ \ \mathrm{páratlan}$
$\sum_{i} H_{i}\ \ \mathrm{páratlan}$

1. példa bemenet

1. 5
2. 1 2 1 1
3. 1 2 2 2
4. 1 2 3 3
5. 1 2 4 4
6. 1 2 5 5

1. példa kimenet

1. 8

2. példa bemenet

1. 5
2. 1 2 1 1
3. 1 2 2 2
4. 1 2 3 3
5. 1 4 4 4
6. 1 4 5 10

2. példa kimenet

1. 12

3. példa bemenet

1. 5
2. 1 2 1 1
3. 1 2 2 2
4. 1 2 3 3
5. 1 4 4 4
6. 1 4 11 10

3. példa kimenet

1. 20