HZNUOJ

曲院风荷

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:157     AC:34     Score:99.07

Description

kk在刷题劳累的时候喜欢去曲院风荷听戏喝茶。kk有一个容量为x个单位的大茶杯,同时kk想喝上一下午,于是他买了n杯茶,每杯茶中有ai个单位的茶水。但是kk有个坏习惯,就是当茶杯里的水倒满的时候kk会倒掉茶杯里的所有茶水(缓慢倒水,水满就倒掉),例如假设往空茶杯中总共加了m个单位的茶水,茶杯中只会剩余m%x单位的茶水。现在kk想知道将n杯茶水选取任意杯茶水倒入茶杯中,最后最多能剩下多少茶水。但是kk太劳累了,所以需要你来帮忙计算剩余茶水的最大值。


Input

单组输入。

每组输入的第一行给出数字n x ,分别代表有n杯茶水和茶杯的容量x单位(1 <=n,<=35, 1<=x<=1000000000)。

接下来一行有n个数字,a1,a2,a3……an代表n杯茶含有的茶水量,(1<=ai<=1000000000)。

Output

输出仅一行,为一个整数t,代表茶杯能剩下的水最多有多少单位。

Samples

input
4 5 1 2 3 4
output
4
input
5 100 9 21 5645 48 6
output
99

Author

XUE, Hongtao