## Editorial for Đổi tiền

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const fi='';
fo='';
maxc=100000;
var n,s,re:longint;
a:array[1..100] of longint;
d:array[1..100] of byte;
f:array[0..1,0..maxc] of longint;

procedure rf;
var i,t:longint;
begin
assign(input,fi);
reset(input);
fillchar(d,sizeof(d),0);
for i:=1 to n do
begin
end;
t:=0;
for i:=1 to 100 do
if d[i]>0 then
begin
inc(t); a[t]:=i;
end;
close(input);
end;

procedure knap;
var i,j,k,cur:longint;
begin
for i:=0 to maxc do f[1,i]:=i;
for i:=2 to n do
begin
cur:=i mod 2;
f[cur]:=f[1-cur];
for j:=1 to maxc do
if (j>=a[i]) and (f[cur,j]>f[cur,j-a[i]]+1) then
f[cur,j]:=f[cur,j-a[i]]+1;
end;
end;

procedure pr;
var i,j:longint;
begin
knap;
if s>maxc then
begin
re:=(s-maxc) div a[n];
if (s-maxc) mod a[n]<>0 then inc(re);
s:=s-re*a[n];
end;
re:=re+f[n mod 2,s];
end;

procedure wf;
begin
assign(output,fo);
rewrite(output);
write(re);
close(output);
end;

begin
rf;
pr;
wf;
end.


#### Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000

int n, a[105], f[22222], s;

int main() {
scanf("%d%d",&n,&s); rep(i,n) scanf("%d",a+i); sort(a,a+n);
int add = 0;
if(s >= 20000) {
add = (s - 20000) / a[n-1];
s -= add * a[n-1];
}
fo(i,1,s) {
f[i] = INF;
for(int j = 0; a[j] <= i && j < n; ++j)
f[i] = min(f[i], f[i-a[j]]+1);
}
printf("%d\n", f[s] + add);
return 0;
}


#### Code mẫu của ladpro98

program dtdoi;
uses    math;
const   maxn=111;
maxV=10000;
oo=1234567890;
fi='';
var     a:array[1..maxn] of longint;
f:array[0..maxn,0..maxV] of longint;
n,s,maxA,res:longint;

procedure input;
var     inp:text;
i:longint;
begin
assign(inp,fi);
reset(inp);
for i:=1 to n do
begin
maxA:=max(maxA,a[i]);
end;
close(inp);
end;

procedure process;
var     i,j,t:longint;
begin
//greedy
if s>maxV then
begin
t:=(s-maxV) div maxA;
s:=s-maxA*(t+1);
res:=t+1;
end;
//dp
f[0,0]:=0;
for j:=1 to s do
f[0,j]:=oo;
for i:=1 to n do
for j:=1 to s do
begin
f[i,j]:=f[i-1,j];
if j>=a[i] then
f[i,j]:=min(f[i,j],f[i,j-a[i]]+1);
end;

end;

begin
input;
process;
write(res+f[n,s]);
end.


#### Code mẫu của RR

//Written by RR
{$R+,Q+} {$Mode objfpc}
{$inline on} uses math; const FINP = ''; FOUT = ''; MAXN = 20111; var f1,f2 : text; n,s : longint; a : array[1..111] of longint; f : array[0..MAXN] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i:longint; begin read(f1,n,s); for i:=1 to n do read(f1,a[i]); end; procedure solve; var i,k:longint; begin fillchar(f,sizeof(f),$77);
f[0]:=0;
for i:=1 to MAXN do
for k:=1 to n do
if a[k]<=i then
f[i]:=min(f[i],f[i-a[k]]+1);

if s<=MAXN then
writeln(f2,f[s])
else
begin
k:=0;
for i:=1 to n do
k:=max(k,a[i]);
i:=MAXN;
while i mod k<>0 do dec(i); i:=i-k+s mod k;
writeln(f2,f[i]+(s-i) div k);
end;
end;

begin
openF;
inp;
solve;
closeF;
end.


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

int main()
{
int n,a[101],S,max = 0,f[10001];
scanf("%d %d",&n,&S);
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>max)
max = a[i];
}
int KQ = 0;
if(S>10000)
{
int d = (S-10000)/max+1;
S = S - max*d;
KQ = KQ+d;
}
f[0] = 0;
for(int i = 1;i<=S;i++)
{
f[i] = 10000;max = 0;
for(int j = 1;j<=n;j++)
{
if(i>=a[j] && f[i]>f[i-a[j]]+1)
f[i] = f[i-a[j]]+1;
}
}
KQ = KQ + f[S];
printf("%d",KQ);
// getch();
}


#### Code mẫu của ll931110

#include <iostream>
#define MAXN 101
#define MAXV 10000
#define MAXK 1000000000
using namespace std;

int F[MAXV],a[MAXN],n,s;

int main()
{
int i,j,k,max,res;

//freopen("dtdoi.inp","r",stdin);
//freopen("dtdoi.out","w",stdout);

scanf("%d%d", &n, &s);
max = 0;
for (i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if (max < a[i] && a[i] <= s) max = a[i];
}

for (i = 0; i < MAXV; i++) F[i] = MAXK;
F[0] = 0;

for (i = 1; i < MAXV; i++)
for (j = 1; j <= n; j++)
if (i >= a[j])
if (F[i] > F[i - a[j]] + 1) F[i] = F[i - a[j]] + 1;

if (s >= MAXV)
{
k = ((s - MAXV) / max) + 1;
s -= k * max;
}
else k = 0;

res = MAXK;
do
{
if (res > k + F[s]) res = k + F[s];
k++;
s -= max;
}
while (s >= 0);

printf("%d", res);
}


#### Code mẫu của skyvn97

#include<cstdio>
#include<algorithm>
#define MAX   111
using namespace std;
const int mdp=60000;
int n,s,mv;
int v[MAX];
int f[MAX][mdp];
void init(void) {
scanf("%d",&n);
scanf("%d",&s);
int i;
mv=-1;
for (i=1;i<=n;i=i+1) {
scanf("%d",&v[i]);
if (v[i]>mv) mv=v[i];
}
sort(&v[1],&v[n+1]);
}
int min(const int &x,const int &y) {
if (x<y) return (x); else return (y);
}
void optimize(void) {
int i,j;
for (i=1;i<=n;i=i+1) f[i][0]=0;
for (i=1;i<mdp;i=i+1) f[1][i]=i;
for (i=2;i<=n;i=i+1)
for (j=1;j<mdp;j=j+1) {
if (j<v[i]) f[i][j]=f[i-1][j];
else f[i][j]=min(f[i-1][j],f[i][j-v[i]]+1);
}
}
if (s<mdp) {
printf("%d",f[n][s]);
return;
}
int i;
int best=(int)1e9;
for (i=s/mv;i>=0;i=i-1) {
if (s-mv*i>=mdp) break;
best=min(best,i+f[n][s-mv*i]);
}
printf("%d",best);
}
int main(void) {
init();
optimize();
return 0;
}


#### Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

#define MAX 100000

int n, s;
int a[111];
int F[MAX + 10];
int main() {
scanf("%d%d", &n, &s);
for(int i=0;i<n;++i) scanf("%d", a + i);
memset( F, 0x1f, sizeof(F));
F[0] = 0;
for(int i=0;i<MAX;++i) {
for(int j=0;j<n;++j)
if(i + a[j] <= MAX)
F[i + a[j]] <?= F[i] + 1;
}
if(s <= MAX) cout << F[s] << endl;
else {
int best = 1000000000;
for(int i=0;i<MAX;++i)
for(int j=0;j<n;++j)
if((s - i) % a[j] == 0)
best <?= F[i] + (s - i) / a[j];
cout << best << endl;
}
// system("pause");
return 0;
}