おいおい,使いかけのペンキの缶を放っておいたら中のペンキが乾いてしまうよ。

57tggx

500pt 5MB 2s

板がn枚あり,i番目の板の面積はsiです。

ペンキの缶がたくさん(加算無限個)あり,1缶分のペンキで面積Sを塗ることができます。

板のうち何枚かを選んで全てペンキで塗り残しなく塗りたいのですが,一度ペンキの缶を開けたら,中身を全て使い切らなければいけません。

塗れる面積の最大値を求めて下さい。

入力

n
s1 s2 … sn
S

制約

1 ≦ n ≦ 100

1 ≦ s1,s2,…,sn ≦ 10000

1 ≦ S ≦ 5000

入力1

5
3 5 6 9 11
5

出力1

25

面積5,9,11の板を選ぶと,ペンキちょうど5缶分を使って面積25が塗れます。

入力2

7
13 25 34 12 23 10 20
74

出力2

0

ペンキを余らせずに塗ることができません。

# Submit

# Submissions Help

Date Language Status Point

# Statistics

AC Count
Shortest Code Size
Shortest Code User