Đề bài

Vào tư thế! Charles và Delila sắp đối đầu trong trận chung kết của giải đấu kiếm Swordmaster.

Dọc theo một bức tường của đấu trường có một giá đựng \(N\) loại kiếm khác nhau; các loại kiếm được đánh số từ \(1\) đến \(N\). Với tư cách trọng tài chính, bạn sẽ chọn một cặp số nguyên \((L, R)\) (với \(1 \le L \le R \le N\)), và chỉ các loại kiếm từ loại thứ \(L\) đến loại thứ \(R\) (tính cả hai đầu) mới được sử dụng trong trận đấu.

Các loại kiếm khác nhau được sử dụng theo những cách khác nhau, và giỏi dùng một loại kiếm không nhất thiết có nghĩa là giỏi dùng một loại khác! Kỹ năng của Charles và Delila với loại kiếm thứ \(i\) lần lượt là \(C_i\) và \(D_i\). Mỗi người sẽ xem xét các loại kiếm mà bạn cho phép sử dụng, rồi chọn loại mà mình thành thạo nhất. Nếu có nhiều loại kiếm được phép mà một đấu thủ có kỹ năng ngang nhau, đồng thời mức kỹ năng đó cao hơn kỹ năng với mọi loại được phép khác, đấu thủ sẽ chọn ngẫu nhiên một trong các loại tốt ngang nhau đó. Charles và Delila có thể chọn cùng một loại kiếm; điều này không thành vấn đề vì mỗi loại đều có nhiều bản sao.

Trận đấu công bằng nếu trị tuyệt đối của hiệu giữa kỹ năng dùng loại kiếm Charles chọn và kỹ năng dùng loại kiếm Delila chọn không vượt quá \(K\). Để trận đấu luôn hấp dẫn, bạn muốn biết có bao nhiêu cặp \((L, R)\) khác nhau tạo ra một trận đấu công bằng.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng chứa \(N\) và \(K\) như trên. Hai dòng tiếp theo lần lượt chứa \(N\) số nguyên \(C_i\) biểu thị kỹ năng của Charles với từng loại kiếm và \(N\) số nguyên \(D_i\) biểu thị kỹ năng của Delila.

Dữ liệu ra

Với mỗi bộ test, in một dòng dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)) và y là số cách chọn tạo ra một trận đấu công bằng.

Ràng buộc

• \(1 \le T \le 100\).
• \(0 \le K \le 10^5\).
• \(0 \le C_i \le 10^5\) với mọi \(i\).
• \(0 \le D_i \le 10^5\) với mọi \(i\).

Phân nhóm

Test set 1 (Hiển thị)

• \(1 \le N \le 100\).

Test set 2 (Ẩn)

• \(N = 10^5\) trong đúng \(8\) bộ test.
• \(1 \le N \le 1000\) trong tất cả các bộ test còn lại ngoài \(8\) bộ test trên.

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

6
4 0
1 1 1 8
8 8 8 8
3 0
0 1 1
1 1 0
1 0
3
3
5 0
0 8 0 8 0
4 0 4 0 4
3 0
1 0 0
0 1 2
5 2
1 2 3 4 5
5 5 5 5 10

Case #1: 4
Case #2: 4
Case #3: 1
Case #4: 0
Case #5: 1
Case #6: 7

Nguồn

Google Code Jam 2019, Vòng 1B, bài Fair Fight.

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