7038: 锁
[Creator : ]
Description
106 号房间共有 $n$ 名居民， 他们每人有一个重要度。
房间的门上可以装若干把锁。假设共有 $k$ 把锁，命名为 $1 \sim k$。每把锁有一种对应的钥匙，也用 $1 \sim k$ 表示。
钥匙可以复制并发给任意多个居民。
每个 106 房间的居民持有若干钥匙，也就是 $1 \sim k$ 的一个子集。如果几名居民的钥匙的并集是 $1 \sim k$，即他们拥有全部锁的对应钥匙，他们都在场时就能打开房门。
新的陆战协定规定，一组居民都在场时能打开房门当且仅当他们的重要度加起来至少为 $m$。
问至少需要给 106 号房间装多少把锁。即，求最小的 $k$，使得可以适当地给居民们每人若干钥匙（即一个 $1 \sim k$ 的子集），使得任意重要度之和小于 $m$ 的居民集合持有的钥匙的并集不是 $1 \sim k$，而任意重要度之和大于等于 $m$ 的居民集合持有的钥匙的并集是 $1 \sim k$。
房间的门上可以装若干把锁。假设共有 $k$ 把锁，命名为 $1 \sim k$。每把锁有一种对应的钥匙，也用 $1 \sim k$ 表示。
钥匙可以复制并发给任意多个居民。
每个 106 房间的居民持有若干钥匙，也就是 $1 \sim k$ 的一个子集。如果几名居民的钥匙的并集是 $1 \sim k$，即他们拥有全部锁的对应钥匙，他们都在场时就能打开房门。
新的陆战协定规定，一组居民都在场时能打开房门当且仅当他们的重要度加起来至少为 $m$。
问至少需要给 106 号房间装多少把锁。即，求最小的 $k$，使得可以适当地给居民们每人若干钥匙（即一个 $1 \sim k$ 的子集），使得任意重要度之和小于 $m$ 的居民集合持有的钥匙的并集不是 $1 \sim k$，而任意重要度之和大于等于 $m$ 的居民集合持有的钥匙的并集是 $1 \sim k$。
Input
第一行两个整数 $n,m\ (0<n<21,\ 0<m<1,000,000,001)$。
第二行 $n$ 个整数表示居民们的重要度。重要度在 $[1,1,000,000,000]$ 之间。
第二行 $n$ 个整数表示居民们的重要度。重要度在 $[1,1,000,000,000]$ 之间。
Output
一个整数表示最少需要多少把锁。
Sample 1 Input
4 3
1 1 1 1
Sample 1 Output
6
106 号房共有 $4$ 名居民，只有 $3$ 人在场时才能打开门。这时共需 $6$ 把锁。