2940. 凤凰古城

单点时限: 2.0 sec

内存限制: 256 MB

凤凰古城,位于沱江之畔,群山环抱,关隘雄奇。碧绿的沱江依着城墙缓缓流淌,叠翠的南华山麓倒映江中。江中渔舟游船数点,山间暮鼓晨钟兼鸣,悬崖上的吊脚楼轻烟袅袅,码头边的浣纱姑笑声朗朗,两岸已有数百年历史的吊脚楼更是别有一番风味。顺水而下穿过虹桥一幅江南水乡的画郑便展现于眼前万寿宫万名塔夺翠楼 …… 一种远离尘世的感觉悠然而生。凤凰,犹如 “ 一幅浓墨浅彩的中国山水画 ”。当你徜徉古城用条石砌成的岩板街时,两边的古建筑各抱地势,鳞次栉比,亭台楼阁重重叠叠,如巨龙飞舞,似鳌鱼展翅。细雨声中,仿佛传来敬香人的牛皮钉鞋敲击街面,发出 “ 叮叮 ” 的响声,使人产生隔世之感。街道两边,有许多屠铺、染坊、制作银器首饰的作坊;各种土特产的店铺,工艺美术店。还有小吃部和酒店,狗肉汤锅香味,包谷烧的醇香使人垂涎。

2011 年暑假,lwc626、haozi、McFn 和 solofandy 组织了一次骑自行车去湖南凤凰古城的活动。假设 ACM/ICPC 实验室有 n 个人,第 i 个人体重是 ci。每辆自行车的载重量都是 K,每车最多载 2 人(一个人骑,另一个坐在后面)。考虑到车多不便于停放,现在请你进行合理安排,既能使用的自行车数量尽量少,又能让大家全体出游一次?

输入格式

第 1 行是一个整数 T 表示测试数据组数

接下来是 T 组测试数据,对于每组数据:

第 1 行有两个整数 N(3< N <1000),K(1< K <1000),分别表示实验室总人数和每辆车的最大载重量

第 2 行有 n 个用空格隔开的整数 ci(i=0..n-1,1<= ci <=K)

输出格式

对于每组测试数据输出一行,每行只有一个数字,即为最少的自行车数。

样例

Input
2
10 8
7 1 4 2 5 3 1 5 4 4
3 10
1 3 5
Output
5
2

98 人解决,106 人已尝试。

110 份提交通过,共有 180 份提交。

2.2 EMB 奖励。

创建: 8 年,1 月前.

修改: 2 年,4 月前.

最后提交: 2 周,2 天前.

来源: ECNU 2011 ACM/ICPC Selective Trials

题目标签