Một số người bán xúc xích đã bắt đầu kinh doanh tại các góc đường (giao lộ) dọc theo một con phố rất dài theo hướng Đông - Tây. Vấn đề là có thể có nhiều người cùng bán tại một góc đường, và khi đó họ sẽ cạnh tranh lẫn nhau. Tuy nhiên, mọi chuyện không hẳn là bế tắc! Những người bán xúc xích đã có một kế hoạch.

Nếu có từ hai người bán trở lên tại cùng một góc đường, thì đúng hai người trong số họ có thể thực hiện một bước di chuyển, nghĩa là:

• Một người di chuyển đến góc đường tiếp theo về phía Đông dọc theo con phố.
• Người kia di chuyển đến góc đường tiếp theo về phía Tây dọc theo con phố.

Hãy nhớ rằng con phố rất dài, vì vậy không có nguy cơ hết góc đường. Cho biết vị trí bắt đầu của tất cả những người bán xúc xích, bạn cần tìm số bước di chuyển tối thiểu họ cần thực hiện trước khi tất cả những người bán được tách rời nhau (nghĩa là mỗi người ở một góc đường khác nhau).

Ví dụ, giả sử con phố bắt đầu với số lượng người bán xúc xích tại mỗi góc đường như sau, liệt kê theo thứ tự từ Tây sang Đông:

... 0 0 2 1 2 0 0 ...

Khi đó, những người bán có thể được tách rời trong 3 bước di chuyển, như hình dưới đây:

... 0 0 2 1 2 0 0 ...
        |
        +--- Do a move here

... 0 1 0 2 2 0 0 ...
          |
          +--- Do a move here

... 0 1 1 0 3 0 0 ...
            |
            +--- Do a move here

... 0 1 1 1 1 1 0 ...

Dữ liệu vào

Mỗi góc đường được gắn nhãn bằng một số nguyên, dương hoặc âm. Với mỗi i, góc đường i+1 là góc đường tiếp theo về phía Đông của góc đường i. Chúng ta sẽ sử dụng hệ thống nhãn này để mô tả các góc đường trong tệp dữ liệu vào.

Dòng đầu tiên của tệp dữ liệu vào chứa số lượng bộ test, \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng số lượng góc đường \(C\) có ít nhất một người bán xúc xích trong cấu hình ban đầu. \(C\) dòng tiếp theo, mỗi dòng chứa một cặp số nguyên cách nhau bởi dấu cách \(P\), \(V\), cho biết có \(V\) người bán tại góc đường \(P\).

Dữ liệu ra

Với mỗi bộ test, xuất một dòng chứa "Case #x: M", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và M là số bước di chuyển tối thiểu cần thực hiện để tất cả người bán kết thúc ở các góc đường khác nhau.

Ràng buộc

• Thời gian giới hạn: 30 giây mỗi bộ test.
• Bộ nhớ giới hạn: 1GB.
• \(1 \le T \le 50\).
• \(1 \le C \le 200\).
• Tất cả các giá trị \(P\) nằm trong khoảng \([-1000000, 1000000]\).
• Trong mỗi bộ test, tất cả các giá trị \(P\) là phân biệt và được liệt kê theo thứ tự tăng dần.
• Tất cả các giá trị \(V\) là số nguyên dương. Giới hạn về tổng của tất cả các giá trị \(V\) được liệt kê bên dưới.
• Luôn có thể tách rời những người bán xúc xích trong một số bước di chuyển hữu hạn.

Phân nhóm

• Small dataset (Test set 1): Tổng số người bán xúc xích trong mỗi bộ test tối đa là 200.
• Large dataset (Test set 2): Tổng số người bán xúc xích trong mỗi bộ test tối đa là 100000.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
3
-1 2
0 1
1 2
2
-1000 1
2000 1

Case #1: 3
Case #2: 0

Nguồn

Google Code Jam 2010, Vòng 3, bài Hot Dog Proliferation.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.