Minimal Hand Strength

You are given a deck with N cards. Each card has two properties: an attack value and a defense value. A hand is defined as any non-empty subset of these cards. The strength of a hand is the absolute difference between the total attack and total defense values of the cards in the hand, that is, if the total attack is \(A\) and the total defense is \(D\), the strength is \(|A - D|\).

Your task is to determine the minimal possible hand strength that can be achieved by choosing any non-empty subset of cards.

Input Constraints: The number of cards (N) is given, followed by N pairs of integers for the cards' attack and defense values.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer (N), representing the number of cards. Each of the following (N) lines contains two space-separated integers denoting the attack and defense values of a card.

outputFormat

Output via standard output (stdout) a single integer representing the minimal hand strength, defined as the minimum absolute difference between the total attack and total defense over all non-empty subsets of cards.## sample

2
7 3
4 5

1