Đổi tiền

View as PDF

Submit solution


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

Author:
Problem types

Bạn được cho một tập hợp các mệnh giá tiền. Tập hợp luôn chứa phần tử mang gía trị 1. Mỗi mệnh giá có vô hạn các đồng tiền mang mệnh giá đó. Cho số tiền ~S~, hãy tìm cách đổi ~S~ thành ít đồng tiền nhất, sao cho mỗi đồng tiền có mệnh giá thuộc vào tập hợp đã cho.

Input

  • Dòng 1: Hai số nguyên dương ~N~ (số phần tử của tập hợp mệnh giá tiền) và ~S~ (số tiền cần đổi) (~1 ≤ N ≤ 100; 1 ≤ S ≤ 10^9~).
  • Dòng 2: ~N~ số nguyên dương biểu thị mệnh giá của các phần tử trong tập hợp (giá trị không vượt quá 100).

Output

  • Dữ liệu ra gồm một số nguyên duy nhất là số đồng tiền ít nhất có thể đổi được.

Input

2 3
1 2

Output

2

Nguồn: SPOJ


Be the first to comment

Comments

There are no comments at the moment.