← 返回题目列表

AtCoder · past23_i

I. 唯一字符数

中文机器翻译题面 查看原题

问题陈述

弦店有卖 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

你可能无法购买任何弦。