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.