Cây ATM trả tiền


Submit solution

Points: 3 (partial)
Time limit: 1.0s
Memory limit: 977M

Author:
Problem type

Cây ATM (máy rút tiền tự động) có n loại mệnh giá tiền \(a_1,a_2,...a_n\) đôi một khác nhau. Bạn được giao nhiệm vụ lập trình cho cây ATM để ai đó nếu muốn rút tiền thì đều được trả tiền sao cho tổng số lượng tờ tiền được trả là ít nhất. Biết rằng số lượng tờ mỗi loại mệnh giá đều là vô hạn

enter image description here

Input

Dòng đầu gồm số nguyên dương n \((1<=n<=1000)\) là số loại mệnh giá và số tiền muốn rút m \((1<=m<=10^5)\)

Dòng tiếp theo gồm n mệnh giá tiền là các số nguyên dương đôi một khác nhau và không vượt quá \(10^4\)

Output

Nếu không có cách đổi tiền thì xuất ra thông báo "ATM khong the tra tien" ngược lại xuất ra số tờ ít nhất

Ví dụ 1:

Input

3 12354

10 65 40

Output

ATM khong the tra tien

Ví dụ 2

Input

3 10

4 1 3

Output

3

Giải thích : Cách trả tiền ở đây 10 tiền thì gồm một tờ 4 và hai tờ 3

tichpx

Comments

There are no comments at the moment.