Sắp tới trường An sẽ có một cuộc đua Marathon tập thể, An đang phân vân trong việc chọn các bạn đi thi. Lớp An có cả học sinh nam và học sinh nữ, mỗi bạn có sức mạnh và độ bền bỉ nhất định. Tuy nhiên sức mạnh và độ bền bỉ của các bạn lại tương khắc với nhau. Nếu sức mạnh lớn hơn nhiều so với độ bền bỉ (hoặc độ bền bỉ lớn hơn nhiều so với sức mạnh) thì sức mạnh tổng hợp sẽ bị giảm xuống đánh kể.

Hiện tại lớp An có tất cả ~n~ bạn. Mỗi bạn có sức mạnh ~s_i~ và độ bền bỉ ~b_i~ đặc trưng. Khi có ~k~ bạn ở chung một đội, sức mạnh của đội sẽ bằng tích sức mạnh của ~k~ bạn, trong khi đó độ bền bỉ sẽ bằng tổng độ bền bỉ của ~k~ bạn.

Để có thể giành giải đồng đội trong cuộc thi này, An phải chọn các bạn sao cho sự chênh lệch giữa độ bền bỉ và sức mạnh là nhỏ nhất.

Dĩ nhiên, An phải chọn ít nhất một bạn học sinh để đi thi đấu. Các bạn hãy giúp An làm thực hiện nhiệm vụ này

Dữ liệu vào:

• Dòng đầu tiên ghi nguyên dương ~n~ là số học sinh lớp An ~(1 ≤ n ≤ 20)~
• ~n~ dòng tiếp theo mỗi dòng gồm 2 số ~s_i~ và ~b_i~ mô tả sức mạnh và độ bền bỉ của học sinh ~i~. ~ ( 0 ≤s_i, b_i ≤ 1000) ~

Dữ liệu đảm bảo ~s_1×s_2×…×s_n ≤ 10^{18}~

Kết quả:

In ra sự chệnh lệch nhỏ nhất giữa sức mạnh và độ bền bỉ của đội thi đấu được chọn

Ví dụ:

Input

4
1 7
2 6
3 8
4 9 

Output

1 

Giải thích

An sẽ chọn 3 bạn học sinh cuối. Sức manh của đội sẽ bằng ~ 2 * 3 * 4 = 24 ~, còn độ bền bỉ là ~ 6+8+9 = 23~. Hiệu của chúng bằng 1.