#5389. Cuộc thi "ĐỒI THUYÊN" (Mã bài: BOATS)

Có người muốn tham gia một cuộc thi thuyền đôi. Người thứ có cân nặng là . Mỗi chiếc thuyền chỉ có thể chở đúng hai người và để công bằng, tất cả các thuyền tham gia phải có tổng trọng lượng hai người trên thuyền bằng nhau.

Yêu cầu: Bạn hãy chọn ra một tổng trọng lượng tối ưu và sau đó thành lập nhiều đội nhất có thể (mỗi đội gồm hai người) sao cho tổng trọng lượng của mỗi đội đều bằng . Hãy tìm số lượng đội tối đa có thể thành lập.

Dữ liệu:

• Dòng đầu tiên chứa số lượng bộ test .
• Mỗi bộ test gồm:
  • Dòng đầu tiên chứa số nguyên .
  • Dòng thứ hai chứa số nguyên .

Kết quả: Với mỗi bộ test, in ra một số nguyên là số đội tối đa có thể thành lập.

Ví dụ:

Dữ liệu:

5
5
1 2 3 4 5
8
6 6 6 6 6 6 8 8
8
1 2 2 3 4 4 5 6
3
1 1 1
6
1 1 2 2 3 3

Kết quả:

2
3
3
1
3

Giải thích: Trong ví dụ đầu tiên, với , . Ta có thể chọn tổng trọng lượng . Khi đó ta có thể tạo 2 đội là và . Đây là số đội tối đa có thể.

Giới hạn:

• .
• .
• .