/ JF_OIer / 题库 /

牛场围栏

牛场围栏

测试数据来自 system/1054

描述

John计划为他的牛场建一个围栏,以限制奶牛们的活动。他有N种可以建造围栏的木料,长度分别是l1,l2…lN,每种长度的木料无限。修建时,他将把所有选中的木料拼接在一起,因此围栏的长度就是他使用的木料长度之和。但是聪明的John很快发现很多长度都是不能由这些木料长度相加得到的,于是决定在必要的时候把这些木料砍掉一部分以后再使用。不过由于John比较节约,他给自己规定:任何一根木料最多只能削短M米。当然,每根木料削去的木料长度不需要都一样。不过由于测量工具太原始,John只能准确的削去整数米的木料,因此,如果他有两种长度分别是7和11的木料,每根最多只能砍掉1米,那么实际上就有4种可以使用的木料长度,分别是6, 7, 10, 11。

Clevow是John的牛场中的最聪明的奶牛,John请她来设计围栏。Clevow不愿意自己和同伴在游戏时受到围栏的限制,于是想刁难一下John,希望John的木料无论经过怎样的加工,长度之和都不可能得到她设计的围栏总长度。

不过Clevow知道,如果围栏的长度太小,John很快就能发现它是不能修建好的。因此她希望得到你的帮助,找出无法修建的最大围栏长度。

格式

输入格式

输入的第一行包含两个整数N, M (1<N<100, 0<=M<3000),分别表示木料的种类和每根木料削去的最大值。以下各行每行一个整数li(1<li<3000),表示第i根木料的原始长度。

输出格式

输出仅一行,包含一个整数,表示不能修建的最大围栏长度。如果任何长度的围栏都可以修建或者这个最大值不存在,输出-1。

样例1

样例输入1

2 1
7 
11

样例输出1

15

限制

各个测试点1秒

来源

WinterCamp 2002

信息

ID
1009
难度
4
分类
其他 | 数学 点击显示
标签
递交数
2
已通过
2
通过率
100%
上传者