Maximizing the Minimum Gain in Bulb Selection

You are given n groups of bulbs. In each group there is one bulb of type A and one bulb of type B, with weights \(a_i\) and \(b_i\) respectively. You may choose to select any bulbs you like; each bulb you select costs \(1\) unit. After you finish selecting bulbs, the system will randomly pick one type (either A or B) and light up all bulbs of that type. For each bulb that is lit and that you selected, you receive a reward equal to its weight.

The bulbs are organized into n groups. In each group you have four choices:

• Do nothing: select no bulb, incurring 0 cost and 0 reward.
• Select the A bulb only: cost 1, rewards: \(a_i\) if A is lit and 0 if B is lit.
• Select the B bulb only: cost 1, rewards: 0 if A is lit and \(b_i\) if B is lit.
• Select both bulbs: cost 2, rewards: \(a_i\) if A is lit and \(b_i\) if B is lit.

Your net outcome depends on the choice made by the system. Let the total reward from type A bulbs be \(X\) and from type B bulbs be \(Y\); note that the total cost incurred is the total number of bulbs chosen, denoted by \(T\). Thus, if A is lit your net gain is \(X-T\) and if B is lit it is \(Y-T\). You want to maximize the minimum gain, that is, maximize

[ M = \min(X-T,, Y-T). ]

Compute the maximum possible value of \(M\) by choosing an optimal set of bulbs.

inputFormat

The first line contains an integer \(n\) (1 ≤ \(n\) ≤ 50), the number of groups.
Then \(n\) lines follow. The \(i\)-th line contains two integers \(a_i\) and \(b_i\) (0 ≤ \(a_i, b_i\) ≤ 100), representing the weights of the A and B bulbs in that group respectively.

outputFormat

Output a single integer, the maximum possible minimum net gain that can be achieved by selecting bulbs optimally.

sample

1
5 4

2