问题陈述
弦店有卖 N 字符串。 的 i- 第一个字符串是 S_i 并售价 X_i 日元(日本货币)。
您将购买零个或更多串,总共最多 Y 日元。 找出购买的字符串中不同字母的最大可能数量。
约束
- 1\leq N \leq 18
- 1 \leq Y \leq 10^9
- S_i 是长度介于 1 和 100,包含在内,由小写英文字母组成。
- 1 \leq X_i \leq 10^9
- 所有输入数字均为整数。
输入
输入由标准输入按以下格式给出:
N Y S_1 X_1 \vdots S_N X_N
输出
将答案打印为整数。
示例输入 1
4 900 apple 300 orange 200 lemon 500 pomegranate 1000
示例输出 1
8
如果您购买 2-nd 和 3-rd 字符串总计 700 日元,它们将包含八个不同的字母: a, e, g, l, m, n, o, r.
示例输入 2
2 200 melon 100 lemon 100
示例输出 2
5
如果您购买 1-st 和 2-根弦,总价为 200 日元,它们将包含五个不同的字母: e, l, m, n, o.
示例输入 3
1 1 abcdefghijklmnopqrstuvwxyz 10000
示例输出 3
0
你可能无法购买任何弦。