TopCoder

WeaK
"中國人有兩種:一種是拿別人吐司的,另一種是不拿自己吐司的" - 邱于賓 2017/04/16

User's AC Ratio

95.2% (20/21)

Submission's AC Ratio

55.4% (41/74)

Tags

Description

有n堆石頭,每堆石頭都有可能混雜著一些黑色石頭或白色石頭。現在請問最少要移動多少個石頭,才能讓每一堆石頭要嘛全是黑色,要嘛全是白色。所謂的移動一個石頭,是指把其中一堆的其中一個石頭搬到另一堆去,你不能丟掉、敲碎、吃掉或者用任何手段銷毀任何一顆石頭,你也不能把石頭移到別的空地去(沒有別的空位啦!)。

Input Format

輸入可能包含多筆測試資料。每一筆測試資料的第一列有一個正整數n (1<=n<=1,000,000),代表石頭的堆數,接下來的n列每列有兩個整數 Bi和 Wi,代表此堆黑色石頭和白色石頭的個數。當n=0時代表輸入結束。每一組測試資料中石頭的總數一定小於231

Output Format

對於每組測試資料,請輸出一個整數代表所需移動的最少石頭個數。如果不管移動多少石頭都沒辦法達成目標,請輸出-1。

Sample Input

3
2 3
4 1
0 5
3
2 3
1 2
0 4
0

Sample Output

3
4

Hints

對於第一筆測試資料:把第一堆的黑色石頭搬到第二堆,然後把第二堆的白色石頭搬到第三堆。至少需要搬動3顆石頭。

Problem Source

原TIOJ1082 / Problem Setter: Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 50
For Testdata: 1 ~ 1, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1500 65536 65536
1 1500 65536 65536