1870: 交换瓷砖

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

农夫约翰想要用他最近从当地店购买的正方形瓷砖来重新装修他的谷仓地板(当然,这家店只售卖正方形物品)。
不幸的是,他在购买之前没有正确测量谷仓的尺寸,因此现在他需要交换一些瓷砖以换取不同尺寸的新正方形瓷砖。
农夫约翰之前购买的N个正方形瓷砖的边长分别为A1, A2, ..., AN。
他想要用新的正方形瓷砖进行交换,以便所有瓷砖的面积之和正好为M。
店家目前提供了一个特别优惠:可以用边长为Ai的瓷砖交换一个边长为Bi的新瓷砖,交换成本为|Ai-Bi|*|Ai-Bi|。
然而,此优惠仅适用于先前购买的瓷砖,农夫约翰不能交换他已经通过交换其他瓷砖获得的瓷砖
(即,不能将尺寸为3的瓷砖交换成尺寸为2的瓷砖,然后将其用于交换尺寸为1的瓷砖)。
请确定交换瓷砖的最小成本,使得所有瓷砖的面积之和为M。
如果无法获得面积为M,则输出-1。

输入格式

第一行为两个正整数N和M,1≤N10,1≤M≤10000。
接下来N行,每行一个正整数Ai,1≤Ai≤100。

输出格式

输出一个数字表示答案。

输入样例 复制

3 6
3
3
1

输出样例 复制

5

数据范围与提示

来源:USACO 2011.11