Lumpy – The Bus Driver

Nguồn: https://www.codechef.com/           

Lumpy là một tài xế xe buýt. Hôm nay, tên lơ xe nghỉ vì vậy Lumpy phải phụ trách luôn công việc của hắn ta. Trên xe buýt có N người. Đôi lúc sẽ có một số người không mang theo tiền thối và không thể trả vừa đúng giá trị của vé xe. Mỗi người trên xe buýt hôm nay vừa phải trả một số tiền lớn hơn giá trị thật sự của vé xe. Bạn được cho biết trước thông tin về số tiền trả thêm của mỗi người thông qua một mảng A có kích thước là N, trong đó A_i là số tiền (số lượng rupee, trong đó rupee là đơn vị tiền tệ của Ấn Độ) mà người thứ i phải trả thêm.

Sau khi kết thúc hành trình, Lumpy để ý rằng anh ta có P đồng mệnh giá một rupee và Q đồng mệnh giá hai rupee. Anh ta muốn thối lại những hành khách của anh ta bằng số tiền này. Vì là một người tốt bụng, Lumpy muốn thối lại đủ tiền cho càng nhiều người càng tốt. Lưu ý rằng Lumpy sẽ không thối lại tiền cho người thứ i nếu anh ta không thể trả đúng số tiền dư với những đồng xu anh ta có.

Lumpy đang bận lái xe buýt và cũng một phần không muốn tính số lượng người tối đa mà anh ta có thể làm hài lòng - Anh ta sẽ gây ra tai nạn nếu anh ta thử làm như vậy. Bạn có thể giúp anh ta với bài toán này?

Dữ liệu vào:

·       Dòng đầu tiên của dữ liệu vào chứa số nguyên T là số lượng bộ test. Mô tả của T bộ test như sau.

·       Với mỗi bộ test, dòng đầu tiên chứa ba số nguyên cách nhau bởi khoảng trắng N, P và Q.

·       Dòng thứ hai chứa N số nguyên cách nhau bởi khoảng trắng, trong đó số nguyên thứ i mô tả A_i.

Dữ liệu ra:

·       Với mỗi bộ test, xuất ra một dòng duy nhất chứa một số nguyên tương ứng với số lượng người tối đa mà Lumpy có thể thối lại.

Ràng buộc:

^·                 1 ≤ T ≤ 10⁶

^·                 1 ≤ N ≤ 10⁵

^·                 1 ≤ A_i ≤ 10⁹

^·                 0 ≤ P, Q ≤ 10¹⁴

^·                 Tổng các giá trị của N trong tất cả các bộ test không vượt quá 10⁶

Subtasks:

Subtask #1 (15 điểm)

·                   P = 0

Subtask #2 (15 điểm)

·                   Q = 0

Subtask #3 (70 điểm)

·       Như ràng buộc gốc

Ví dụ:

Input

3

3 3 0

1 2 2

3 2 1

1 2 1

4 5 4

2 3 4 5

Output

2

3

3

Giải thích:

Trong test 1, Lumpy vừa có 3 đồng với mệnh giá một rupee.

Anh ta có thể trả những người có số hiệu {1, 2} hoặc những người có số hiệu {1, 3} với những đồng tiền này. Vì vậy, câu trả lời là 2.

Trong test 2, Lumpy có 2 đồng mệnh giá một rupee và 1 đồng mệnh giá hai rupee.

Trong phương án tối ưu, Lumpy có thể đưa đồng mệnh giá hai rupee cho người thứ 2 và những đồng mệnh giá một rupee cho người thứ 1 và 3. Vì vậy kết quả là 3.