どの文字列を購入するかを \(2^N\) 通り全探索します。 購入する文字列の集合を決めたとき、それらが予算内に収まるかどうかと、何種類の文字が含まれるかをそれぞれ愚直に調べます。これには文字列の長さの最大値を \(L\) として \(O(NL)\) 時間かかるため、全体で \(O(2^N NL)\) 時間でこの問題を解くことができます。

なお、あらかじめ各文字列から重複する文字を取り除くことで、文字列の長さは全体の文字種数以下であるとしてよく、全体の文字種数を \(\sigma\) として、\(O(2^N N\sigma)\) で解くこともできます。さらに、bit演算を用いて \(O(2^N N)\) で解くこともできます。

writer解(C++)(bit演算を用いた高速化を行う実装)

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,l,r)for(int i=(l);i<(r);i++)
#define bit(s,k)(((s)>>(k))&1)

int main(){
	int n,y;
	cin >> n >> y;
	vector<int>s(n);
	vector<int>x(n);
	rep(i,0,n){
		string ss;
		cin >> ss >> x[i];
		for(auto c:ss)s[i]|=1<<(c-'a');
	}
	
	int ans=0;
	rep(i,0,1<<n){
		int ss=0;
		ll xx=0;
		rep(k,0,n)if(bit(i,k)){
			xx+=x[k];
			ss|=s[k];
		}
		if(xx<=y)ans=max(ans,__builtin_popcount(ss));
	}
	
	cout << ans << endl;
}