Để chào đón người tham dự một hội nghị dành cho lập trình viên trên Io, vệ tinh của Sao Mộc, ban tổ chức đã bơm rất nhiều bóng bãi biển khổng lồ. Mỗi quả bóng có hình gần giống chữ số \(1\) hoặc \(0\), bởi chúng trông hơi giống các chữ I và O. Hội nghị vừa kết thúc nên giờ phải dọn hết bóng. May thay, robot dọn bóng BALL-E đã nhận nhiệm vụ!

Hội nghị được tổ chức trên một đường thẳng ngang vô hạn, với trạm \(0\) ở giữa, các trạm \(1,2,\ldots\) ở bên phải và các trạm \(-1,-2,\ldots\) ở bên trái. Trạm \(0\) chứa kho bóng duy nhất của hội nghị. Mỗi trạm khác chứa nhiều nhất một quả bóng.

BALL-E có hai ngăn chứa, mỗi ngăn đựng được một quả bóng. Một ngăn chỉ đựng bóng hình \(1\), ngăn kia chỉ đựng bóng hình \(0\). Bóng hình \(1\) thuôn dài hơn bóng hình \(0\), nên bóng của mỗi hình không thể vừa ngăn dành cho hình kia.

Ban đầu, cả hai ngăn \(0\) và \(1\) của BALL-E đều trống, và robot xuất phát tại trạm \(0\). Robot có thể thực hiện các thao tác sau:

• Di chuyển sang trạm liền kề bên trái hoặc bên phải, tốn \(1\) đơn vị năng lượng.
• Nếu trạm hiện tại có bóng và BALL-E chưa mang bóng cùng hình, robot có thể cất bóng đó vào ngăn tương ứng, tốn \(0\) năng lượng.
• Nếu trạm hiện tại có bóng, BALL-E có thể nén để đổi bóng sang hình còn lại: bóng hình \(1\) thành hình \(0\) hoặc ngược lại. Thao tác tốn \(C\) năng lượng. BALL-E không thể đổi hình một quả bóng đã được cất trong ngăn.
• Nếu BALL-E đang ở trạm \(0\) và mang ít nhất một bóng, robot có thể gửi toàn bộ bóng trong các ngăn vào kho. Thao tác tốn \(0\) năng lượng và để cả hai ngăn trống.

Lưu ý rằng khi BALL-E tới một trạm có bóng, robot không bắt buộc phải nhặt bóng ngay, ngay cả khi ngăn tương ứng còn trống. Tương tự, khi đến trạm có kho, robot không bắt buộc phải gửi những quả bóng đang mang.

Hãy tìm số đơn vị năng lượng nhỏ nhất để BALL-E chuyển tất cả bóng vào kho, chỉ sử dụng các thao tác trên.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(N\) và \(C\): số quả bóng và số đơn vị năng lượng cần để đổi hình một quả bóng. \(N\) dòng tiếp theo mô tả vị trí (số trạm) và hình của các quả bóng. Dòng thứ \(i\) chứa hai số nguyên \(X_i,S_i\), lần lượt là vị trí và hình của quả bóng thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ \(1\), và \(y\) là số đơn vị năng lượng nhỏ nhất cần để chuyển toàn bộ bóng vào kho như mô tả.

Ràng buộc

• \(1\le T\le100\).
• \(0\le S_i\le1\) với mọi \(i\).
• \(-10^9\le X_i\le10^9\) với mọi \(i\).
• \(0\le C\le10^9\).
• \(X_i\ne0\) với mọi \(i\).
• Mọi \(X_i\) đôi một khác nhau.

Phân nhóm

• Test Set 1 (phán quyết hiển thị): trong nhiều nhất \(15\) test, \(1\le N\le5000\); trong các test còn lại, \(1\le N\le100\).
• Test Set 2 (phán quyết ẩn): trong nhiều nhất \(15\) test, \(1\le N\le10^5\); trong các test còn lại, \(1\le N\le5000\).

Đ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ụ

4
5 0
3 0
6 0
8 0
10 1
15 1
5 10
3 0
6 0
8 0
10 1
15 1
5 1
3 0
6 0
8 0
10 1
15 1
2 0
1000000000 0
-1000000000 1

Case #1: 52
Case #2: 56
Case #3: 54
Case #4: 4000000000

Nguồn

Google Code Jam 2022, Vòng 2, bài I, O Bot.

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