Đề bài

Bạn thuộc nhóm nghiên cứu khí hậu dọc bờ một hòn đảo. Bờ biển được mô hình hóa bằng đường tròn chu vi \(K\) ki-lô-mét. Một ngọn hải đăng chiếm đúng một điểm trên đường tròn. Mỗi điểm được ánh xạ tới số thực trong \([0,K)\); điểm \(x\) cách hải đăng \(x\) ki-lô-mét khi đi theo chiều kim đồng hồ. Ví dụ, nếu \(K=5\), điểm \(0\) là hải đăng, điểm \(1.5\) cách nó \(1.5\) ki-lô-mét theo chiều kim đồng hồ, còn điểm \(2.5\) đối diện nó qua đường kính.

Bạn phụ trách nghiên cứu nhiệt độ ven biển. Nhóm khác lắp hệ thống gồm một số nhiệt kế tại các điểm cụ thể; không có hai chiếc cùng vị trí. Điểm không có nhiệt kế được coi là mang nhiệt độ của nhiệt kế gần nhất. Nếu cách đều hai nhiệt kế, hệ thống dùng chiếc nằm theo chiều kim đồng hồ (chiếc đầu tiên gặp khi đi từ điểm ấy theo chiều kim đồng hồ).

Bạn không biết số lượng và vị trí nhiệt kế nhưng có dữ liệu gồm hai danh sách \(N\) giá trị \(X_1,\ldots,X_N\) và \(T_1,\ldots,T_N\). Với \(1\le i<N\), mọi \(x\) thỏa \(X_i\le x<X_{i+1}\) mang nhiệt độ \(T_i\); mọi \(x\) thỏa \(0\le x<X_1\) hoặc \(X_N\le x<K\) mang \(T_N\). Các điểm được liệt kê theo chiều kim đồng hồ nên \(X_i<X_{i+1}\) với mọi \(i\).

Hãy tìm số nhiệt kế nhỏ nhất có thể tạo ra dữ liệu quan sát được khi đặt tại một tập vị trí nào đó.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm ba dòng. Dòng đầu chứa hai số nguyên \(K,N\): chu vi đảo và kích thước các danh sách. Dòng hai chứa \(N\) số nguyên \(X_1,\ldots,X_N\). Dòng ba chứa \(N\) số nguyên \(T_1,\ldots,T_N\). Cách chúng biểu diễn nhiệt độ đã giải thích ở trên.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)), còn y là số nhiệt kế nhỏ nhất có thể tạo ra dữ liệu đầu vào.

Ràng buộc

• \(1\le T\le100\).
• \(2\le N\le\min(100,K)\).
• \(0\le X_1\).
• \(X_i<X_{i+1}\) với mọi \(i\).
• \(X_N<K\).
• \(184\le T_i\le330\) với mọi \(i\).
• \(T_i e T_{i+1}\) với mọi \(i\).
• \(T_1 e T_N\).

Phân nhóm

Test Set 1 (Phán quyết hiển thị)

• \(2\le K\le10\).

Test Set 2 (Phán quyết ẩn)

• \(2\le K\le10^9\).

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

Ví dụ

3
2 2
0 1
184 330
3 2
0 1
184 330
10 3
1 5 9
184 200 330

Case #1: 2
Case #2: 3
Case #3: 3

Nguồn

Google Code Jam 2020, Vòng 3, bài Thermometers.

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