时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
众所周知，牛妹是一个魔法少女。
众所周知，相遇就是缘分。
今天恰巧七夕节，牛妹想要挑选自己的如意郎君了。因为牛妹是一个魔法少女，所以不是谁都可以通过牛妹的考验的。
牛妹有一本魔法字典书，这个书上有N个魔法字符串，每个魔法字符串阅读之后都会损耗一定的魔法或者得到一定的魔法(权值有正负)。现在牛妹要阅读一个长度为L的魔法密语，你能构造出一个长度为L的密语使得牛妹读完密语之后获得魔法值最多嘛？
注意：阅读魔法密语时考虑包含情况，即阅读abc也阅读了ab
牛牛接受了这个挑战，他要求自信满满的在七夕节这天去追牛妹！
众所周知，牛牛是不可能自己完成的，这时候就需要机智的你来帮助他。
最后，牛妹降低了要求，只需要求出最多的魔法值就可以认为牛牛已经构造出了魔法密语。
最后的最后，魔法密语必须要求26个小写字母组成
输入描述:
第一行包含两个数字：N，L(N<=200,L<=1000)
接下来N行每行一个字符串s,一个权值val，分别代表魔法字符串与该魔法字符串会损失/得到的魔法
数据保证，并且s均为小写字母构成
输出描述:
一个数字，代表魔法密语能获得的最大魔法值