Bīngqílín Critic
Xem dạng PDF
Bīngqílín 2023 là loại kem ngon nhất mà tôi đã từng trải nghiệm!
— Nhà phê bình Bīngqílín, Quatkun
Nhà phê bình Bīngqílín Quatkun sau biết tin cửa hàng kem Bedao mở cửa đã liền đến thăm cửa hàng. Sau khi thưởng thức món kem Bīngqílín 2023 độc nhất, nhà phê bình đã dành rất nhiều lời khen cho cửa hàng trong bài phê bình của mình. Tuy vậy cửa hàng còn rất nhiều loại kem, nên Quatkun vẫn muốn thưởng thức thêm. Lần này Quatkun muốn ăn thật nhiều kem để đánh giá độ phong phú đa dạng các loại kem của cửa hàng.
Bedao rất thích tin học và làm việc với những con số, nên không chỉ có
mỗi Bīngqílín 2023 là có những viên kem có họa tiết là các con số ~2~,
~0~, ~2~ và ~3~, mà những loại kem khác cũng đều có họa tiết như vậy,
điển hình như Bīngqílín bảy sắc cầu vồng
1234567,
Bīngqílín thập cẩm ~9876543210~ và Bīngqílín mod FFT ~998\,244\,353~.
Trong cửa hàng Bedao có ~n~ loại kem. Loại kem thứ ~i~ giá là ~c_i~
Coin một cây, và có chỉ số họa tiết là ~d_i~ (tức họa tiết của
loại kem này sẽ được biểu diễn bởi số ~d_i~).
Hôm nay cửa hàng kem Bedao còn có một chương trình ưu đãi đặc biệt: nếu như tổng chỉ số họa tiết của những cây kem đã được mua hôm nay là một số chia hết cho ~3~, khách hàng sẽ được tặng một voucher giảm giá kem Bīngqílín 2023 trong ~3~ ngày tới.
Dĩ nhiên Quatkun vừa muốn thưởng thức thật nhiều loại kem, vừa muốn có
chiếc voucher. Cho danh sách giá thành và chỉ số họa tiết của các loại
kem trong cửa hàng, và ~k~ là lượng Coin mà Quatkun đang giữ,
hãy tìm số lượng loại kem nhiều nhất mà Quatkun có thể thưởng thức, sao
cho tổng giá trị các cây kem không quá ~k~, đồng thời giúp Quatkun có
được voucher từ cửa hàng.
Input
Dòng đầu tiên của test case chứa hai số nguyên ~n~ và ~k~
(~1 \le n \le 100\,000~, ~1 \le k \le 10^{15}~) – số lượng loại
kem trong cửa hàng và số lượng Coin của Quatkun.
Dòng thứ hai của test case chứa ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ (~1 \le c_i \le 10^9~) – giá thành của mỗi loại kem trong cửa hàng.
Dòng thứ ba của test case chứa ~n~ số nguyên ~d_1, d_2, \ldots, d_n~ (~1 \le d_i \le 10^9~) – chỉ số họa tiết của các loại kem trong cửa hàng.
Output
Với mỗi test case, in ra một số nguyên duy nhất là số lượng loại kem mà Quatkun có thể thưởng thức mà vẫn có thể nhận được voucher từ cửa hàng. Nếu không có cách nào mua kem mà giúp Quatkun nhận được voucher, hãy in ra ~0~.
Scoring
Subtask 1 (~200~ điểm): ~n \le 20~ và ~k \le 200~.
Subtask 2 (~300~ điểm): ~n, k \le 200~.
Subtask 3 (~500~ điểm): không có ràng buộc gì thêm.
Tổng cộng bài toán có ~1000~ điểm.
Sample Input 1
3 10
2 3 4
3 1 2
Sample Output 1
3
Sample Input 2
3 7
2 3 4
3 1 2
Sample Output 2
2
Sample Input 3
1 100
1
1
Sample Output 3
0
Notes
Ở ví dụ đầu tiên có ~3~ cây Bīngqílín. Tổng giá trị của ~3~ cây
Bīngqílín này là ~9~ coin, và tổng chỉ số họa tiết của chúng
là ~6~, là một số chia hết cho bar. Vì Quatkun mang theo mình ~10~
coin, nên Quatkun có thể thưởng thức hết cả ~3~ cây Bīngqílín
này.
Ở ví dụ thứ hai, các cây kem giống ở ví dụ đầu tiên. Tuy nhiên Quatkun
chỉ đem theo mình ~7~ coin. Sự lựa chọn tối ưu cho Quatkun là ăn
cây kem thứ hai và thứ ba, với tổng giá trị là ~3 + 4 = 7~ coin,
và tổng chỉ số họa tiết là ~1 + 2 = 3~.
Ở ví dụ thứ bar, tuy Quatkun mang theo mình đến ~100~ coin, tuy
nhiên trong cửa hàng còn có mỗi một cây Bīngqílín, và cây Bīngqílín
này lại có chỉ số họa tiết là ~1~, nên không có cách nào giúp Quatkun
nhận được voucher.
Bình luận
Ai gợi ý cách giải được ko, mình có nghĩ đến chặt nhị phân nhưng chưa biết triển khai như nào cho tối ưu
mình sài qhđ ăn được sub12
xin chao NSG
mua kem đâu vậy ạ?