#P6927. 锁

    ID: 6758 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>CF1900普及+/提高-补集转化全子集枚举子集 DP

锁

题目描述

一间房子里有 nn 位居民,每位居民有一个重要度 aia_i。房门可以装若干把锁。每把锁有独立的钥匙,钥匙可复制任意份,并发给任意居民。一位居民可以持有多种钥匙,也可以没有钥匙。

一组居民可以打开房门,当且仅当他们持有的钥匙合在一起能打开所有的锁。要求每组居民能够打开门,当且仅当这组居民的重要度总和至少为 mm。

求满足要求的最少锁数。

输入格式

第一行两个整数 n,mn,m。第二行 nn 个整数 aia_i,依次表示各居民的重要度。

输出格式

一行一个整数,表示最少锁数。

样例

4 3
1 1 1 1
6

数据范围

  • 对于 30%30\% 的数据,所有 ai=1a_i=1。
  • 另有 30%30\% 的数据,1≤n≤81\le n\le8。
  • 对于所有数据,1≤n≤201\le n\le20,1≤m≤1091\le m\le10^9,ai≤ma_i\le m。现有评测数据中的 aia_i 均为正整数。

原 PDF 题面