#P6927. 锁
锁
题目描述
一间房子里有 位居民,每位居民有一个重要度 。房门可以装若干把锁。每把锁有独立的钥匙,钥匙可复制任意份,并发给任意居民。一位居民可以持有多种钥匙,也可以没有钥匙。
一组居民可以打开房门,当且仅当他们持有的钥匙合在一起能打开所有的锁。要求每组居民能够打开门,当且仅当这组居民的重要度总和至少为 。
求满足要求的最少锁数。
输入格式
第一行两个整数 。第二行 个整数 ,依次表示各居民的重要度。
输出格式
一行一个整数,表示最少锁数。
样例
4 3
1 1 1 1
6
数据范围
- 对于 的数据,所有 。
- 另有 的数据,。
- 对于所有数据,,,。现有评测数据中的 均为正整数。