Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P134SUMG - SUM4 G - Gia vị

Tại một nhà hàng truyền thống của Ấn Độ, đầu bếp đang phân vân trong việc chọn gia vị cho món ăn của mình. Nhà hàng này rất nổi tiếng bởi bí quyết gia vị của họ, đặc biệt là vị chua và vị cay. Các món ăn của họ có vị chua và cay xen lẫn nhau rất đặc biệt.

Hiện tại đang có tất cả N loại gia vị. Mỗi loại có độ chua S_i và độ cay B_i đặc chưng. Khi trộn K loại gia vị vào món ăn, độ chua của món ăn sẽ bằng tích độ chua của K loại gia vị, trong khi đó độ cay sẽ bằng tổng độ cay của K loại gia vị.

Để cho món ăn được hấp dẫn và hài hòa, đầu bếp sẽ chọn các loại gia vị sao cho sự chênh lệch giữa độ chua và độ cay của món ăn là nhỏ nhất.

Dĩ nhiên, cần phải chọn ít nhất một loại gia vị cho món ăn. Các bạn hãy giúp đầu bếp thực hiện công việc này.

Input

Dòng đầu tiên là số thành phần gia vị N (1 ≤ N ≤ 10).

N dòng tiếp theo, mỗi dòng gồm 2 số S_i, B_i mô tả đặc trưng vị chua và vị cay của gia vị đó.

Input được đảm bảo rằng nếu trộn tất cả các loại gia vị, thì độ cay và độ chua của món ăn sẽ nhỏ hơn 10^9.

Output

In ra sự chênh lệch nhỏ nhất giữa vị chua và vị cay của món ăn.

Example

Test 1:

Input:

1

3 10

Output:

7

 

Test 2:

Input:

2
3 8
5 8

Output:

1

 

Test 3:

Input:

4
1 7
2 6
3 8
4 9

Output:

1

 

Giải thích test 3: Đầu bếp sẽ chọn 3 gia vị cuối. Độ chua của món ăn sẽ bằng 2*3*4 = 24, còn độ cay là 6+8+9 = 23. Hiệu của chúng bằng 1.


Được gửi lên bởi:adm
Ngày:2013-07-31
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2020-04-08 08:38:20
tham khảo lời giải tại :http://codepad.org/OgxBfEiq

Last edit: 2020-04-15 15:40:36
2019-07-09 04:10:32
trưng & chưng

2017-04-17 20:24:10
sinh
2015-02-22 07:57:25 Con Bò Huyền Thoại
http://kienthuc24h.com/p134sumg-ptit-spoj-sum4-g-gia-vi/

Last edit: 2015-04-30 05:00:31
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.