Bedao Mini Contest 12 - MUSCULAR

View as PDF

Submit solution


Points: 0.10 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Am hiểu sâu sắc và có lòng tin mãnh liệt vào phương pháp bảo vệ sức khỏe bằng tập luyện TDTT, Bác Hồ khuyên mỗi người dân: "Mỗi ngày lúc ngủ dậy, tập một ít thể dục. Ngày nào cũng tập, khí huyết lưu thông, tinh thần đầy đủ, như vậy là sức khỏe…" . Điều Bác nói cách chúng ta hơn nửa thế kỷ này lại rất gần với định nghĩa về sức khỏe của Tổ chức Y tế thế giới ngày nay "Sức khoẻ là một trạng thái hoàn toàn thoải mái cả về thể chất, tâm thần và xã hội, chứ không phải là chỉ là không có bệnh tật hay tàn phế".

Chính vì thế, Copium luôn chăm chỉ rèn luyện sức khỏe mỗi ngày. Ở phòng tập có ~n~ quả tạ được đánh số từ ~1~ đến ~n~, mỗi quả tạ đều được ghi số cân nặng lần lượt là ~w_1, w_2, \dots, w_n~. Copium vốn là một gymer nổi tiếng với biệt tài nâng được ~3~ quả tạ cùng lúc mà không ai có thể làm được. Bên cạnh đó, do tập tạ đã lâu nên Copium có thể nâng tổng cân nặng lên tới ~M~. Là một stalker fan hâm mộ nhiệt thành của Copium, bạn hãy tính với nhiều nhất là ~3~ quả tạ từ số tạ cho trước, Copium có thể nâng bao nhiêu hạng cân khác nhau bé hơn hoặc bằng ~M~.

Biết rằng hạng cân chính là tổng số cân từ các quả tạ mà Copium phải nâng.

Input

  • Dòng đầu tiên gồm hai số nguyên ~n~ ~(1 \leq n \leq 300)~ và ~M~ ~(1 \leq M \leq 10^6)~.
  • Dòng thứ hai bao gồm ~n~ số nguyên là ~w_1, w_2, \dots, w_n~ ~(1 \leq w_i \leq 10^6)~.

Output

  • Gồm một số nguyên duy nhất là số hạng cân khác nhau bé hơn hoặc bằng ~M~ mà Copium có thể nâng được.

Sample Input

4 16
5 5 5 5

Sample Output

3

Note

Bạn đã dành ra một ngày theo dõi và biết được rằng với số tạ có số cân cho trước lần lượt là ~[5, 5, 5, 5]~ thì Copium có thể nâng được các hạng cân khác nhau lần lượt từ ~5~, ~10~, ~15~. Vì các số này đều bé hơn hoặc bằng tổng cân nặng mà Copium có thể nâng được là ~16~ nên có tổng cộng ~3~ hạng cân khác nhau.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.