Đất nước Fairland có những luật rất nghiêm ngặt về cách các công ty tổ chức và trả lương cho nhân viên:

1. Mỗi công ty phải có đúng một CEO, người không có quản lý.
2. Mọi nhân viên trừ CEO phải có đúng một quản lý. Vì thế sơ đồ tổ chức gồm toàn bộ nhân viên là một cây, không có chu trình.
3. Trong suốt thời gian một nhân viên còn làm việc cho công ty, quản lý của họ không bao giờ được thay đổi. Do đó, nếu một quản lý rời công ty thì tất cả nhân viên báo cáo cho người đó cũng phải rời công ty.
4. CEO không bao giờ được rời công ty.
5. Mỗi nhân viên nhận một mức lương, tức một số đô-la Fairland mỗi năm. Lương của một nhân viên không bao giờ được thay đổi.
6. Các nhân viên khác nhau có thể có mức lương khác nhau, và lương của một nhân viên không nhất thiết liên quan đến vị trí của họ trong sơ đồ tổ chức.

Chính phủ Fairland vừa thông qua thêm một luật:

1. Chênh lệch giữa mức lương lớn nhất và nhỏ nhất trong toàn công ty không được vượt quá \(D\) đô-la Fairland.

Marie là CEO của Fairland General Stuff Corporation và phải bảo đảm công ty tuân thủ luật mới. Điều này có thể buộc cô phải cho một số nhân viên nghỉ việc. Marie có danh sách nhân viên, quản lý và mức lương của họ. Hãy tìm số nhân viên lớn nhất cô có thể giữ lại, tính cả chính cô.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng gồm hai số nguyên \(N\) (số nhân viên) và \(D\) (chênh lệch lương tối đa được phép). Tiếp theo là một dòng chứa bốn số nguyên \(S_0,A_s,C_s,R_s\), rồi một dòng chứa bốn số nguyên \(M_0,A_m,C_m,R_m\). Tám số cuối xác định hai dãy:

Marie có ID 0; các nhân viên còn lại có ID từ 1 đến \(N-1\). Lương của nhân viên \(i\) là \(S_i\). Với mọi nhân viên \(i\) khác Marie, quản lý của họ là \(M_i\bmod i\). Lưu ý rằng \(M_0\) không ảnh hưởng đến quản lý của Marie vì cô không có quản lý.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), còn \(y\) là số nhân viên lớn nhất Marie có thể giữ lại trong công ty, tính cả cô, sao cho cả bảy luật đều được tuân thủ.

Ràng buộc

• \(1\le T\le100\).
• \(0\le S_0<R_s\).
• \(0\le M_0<R_m\).
• \(0\le A_s,A_m\le1000\).
• \(0\le C_s,C_m\le10^9\).

Phân nhóm

• Tập nhỏ: \(1\le N\le1000\); \(1\le D\le1000\); \(1\le R_s,R_m\le1000\).
• Tập lớn: \(1\le N\le10^6\); \(1\le D\le10^6\); \(1\le R_s,R_m\le10^6\).

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

3
1 395
18 246 615815 60
73 228 14618 195
6 5
10 1 3 17
5 2 7 19
10 13
28 931 601463 36
231 539 556432 258

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

Nguồn

Google Code Jam 2015, Vòng 3, bài Fairland.

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