Задача C. Геройская армия ≡

Условие

Слон Пахом любит играть в игру "Герои меча и магии". У Пахома есть N героев. У каждого героя в армии содержится ровно 7 различных видов существ (существ одного вида может быть много). Всего в игре существует 14 различных существ (7 видов, 1-го или 2-го уровня). У каждого существа есть сила p_i. Существа первого и второго уровня считаются различными, и их нельзя объединять без предварительного улучшения существ 1-го уровня до 2-го. Сила существа второго уровня не меньше силы того же существа первого уровня. Существа первого уровня обозначаются маленькими буквами латинского алфавита (a, b, c, d, e, f, g), второго — большими буквами латинского алфавита (A, B, C, D, E, F, G). Любое существо 1-го уровня можно улучшить до 2-го уровня потратив c_i денег. Пахому лень разделять группы существ, поэтому он может улучшить группу существ в какой либо армии только полностью. Улучшения происходят следующим образом a->A, b->B, c->C и т.д.

Пахому предстоит отправиться на завоевание замка, поэтому ему нужно снарядить сильной армией одного героя. Для этого Пахом может перемещать группы существ между различными героями. Перемещение существ происходит бесплатно. Если два героя имеют группы существ одного вида, один из них может передать всех существ данного вида другому герою. Если же два героя имеют группы существ разного вида, они могут поменяться этими группами существ.

Наиболее сильную армию можно было бы получить, улучшив всех существ и собрав армию из 7 видов существ 2-го уровня. Однако на это может не хватить монет, поэтому необходимо выбрать, какие группы существ улучшать. Помогите Пахому собрать максимально сильную армию и при этом потратить не более M монет.

Формат входного файла

Первая строка входного файла содержит два числа N и M, количество героев и количество денег игрока.

Вторая строка содержит 14 чисел p_i, мощность одного существа видов a, b, c, d, e, f, g, A, B, C, D, E, F, G. соответственно.

Третья строка содержит 7 чисел с_i, стоимость улучшения одного существа видов a, b, c, d, e, f, g, соответственно.

Далее следует N строк, каждая строка содержит 7 пар, t_ij q_ij — вид существа и количество существ этого вида у i-го героя.

Формат выходного файла

Выходной файл должен содержать одно число — максимальную силу собранной армии.

Ограничения

1 ≤ N ≤ 50

0 ≤ M ≤ 5000

0 ≤ p_i, c_i, q_i ≤ 1000

Примеры тестов

2 10
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1
a 5 b 5 c 6 d 6 e 6 f 7 g 8
A 10 B 10 C 10 D 10 E 10 F 10 G 10

80

2 50 
0 1 2 3 4 5 6 1 2 3 4 5 6 7
1 1 1 1 1 1 1
A 10 B 20 C 30 D 40 E 50 F 60 G 70
a 400 B 300 C 100 D 100 E 100 F 400 G 500

9100

3 50 
0 1 2 3 4 5 6 1 2 3 4 5 6 7
1 1 1 1 1 1 1
a 1000 b 500 c 0 d 0 e 0 f 0 g 0
A 10 B 20 C 30 D 40 E 50 F 60 G 70
a 400 B 300 C 100 D 100 E 100 F 400 G 500

9590