/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
問題文
文字列屋さんに N 個の文字列が売られています。i 番目の文字列は S_i であり、値段は X_i 円です。
Y 円以内でいくつか( 0 個でもよい)の文字列を購入するとき、購入した文字列のいずれかに含まれる文字の種類数の最大値を求めてください。
制約
- 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,3 番目の文字列を 700 円で購入すると a, e, g, l, m, n, o, r の 8 種類の文字が含まれます。
入力例 2
2 200 melon 100 lemon 100
出力例 2
5
1,2 番目の文字列を合計 200 円で購入すると e, l, m, n, o の 5 種類の文字が含まれます。
入力例 3
1 1 abcdefghijklmnopqrstuvwxyz 10000
出力例 3
0
文字列を 1 つも購入できないこともあります。
Problem Statement
A string shop sells N strings. The i-th string is S_i and sold for X_i yen (the currency in Japan).
You will buy zero or more strings for a total of at most Y yen. Find the maximum possible number of distinct letters in the bought strings.
Constraints
- 1\leq N \leq 18
- 1 \leq Y \leq 10^9
- S_i is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.
- 1 \leq X_i \leq 10^9
- All input numbers are integers.
Input
The input is given from Standard Input in the following format:
N Y S_1 X_1 \vdots S_N X_N
Output
Print the answer as an integer.
Sample Input 1
4 900 apple 300 orange 200 lemon 500 pomegranate 1000
Sample Output 1
8
If you buy the 2-nd and 3-rd strings for a total of 700 yen, they will contain eight distinct letters: a, e, g, l, m, n, o, r.
Sample Input 2
2 200 melon 100 lemon 100
Sample Output 2
5
If you buy the 1-st and 2-nd strings for a total of 200 yen, they will contain five distinct letters: e, l, m, n, o.
Sample Input 3
1 1 abcdefghijklmnopqrstuvwxyz 10000
Sample Output 3
0
You may not be able to buy any strings.