Vote

There’s an election in Peter’s city: two parties, A and B are fighting for power.

In the city there are

N

districts, in the

i

th district there are

V_i

voters (

i=1\ldots N

). By winning the

i

th district a party can delegate

H_i

members to the city council. You win the district if you have the majority of the votes in it and you win the election by delegating the majority of the members of the city council. It is known that for the

i

th district, that

G_i

golden coins are required for one voter to change his voting preferences. From opinion polls, we know that without any interference, in the

i

th district

A_i

people would vote for party A and

B_i

people would vote for party B (

V_i=A_i+B_i

). Peter wants Party A to win the election. Please calculate

M

: the minimal amount of golden coins party A needs to spend to win the election.

Input specification

In the first line there is a number $N$ . Then $N$ lines follow with four numbers each - $A_i\ B_i\ H_i\ G_i\$ - describing the situation in the $i$ th district $(i=1\ldots N)$ .

Output specification

A single line with the number $M$

Constraints

$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{is\ odd}$
$\sum_{i} H_{i}\ \ \mathrm{is\ odd}$