Когда Кефа пришел в ресторан и уселся за столик, официант сразу же принес ему меню. Там оказалось целых n блюд. Кефа знает, что ему нужно ровно m порций, чтобы насытиться. Но при этом он не хочет заказывать одно и то же дважды, чтобы попробовать максимальное количество блюд.
Кефа знает, что i-е блюдо поднимет его удовлетворенность на ai. Но некоторые блюда плохо сочетаются друг с другом, а некоторые — наоборот хорошо. Кефа установил себе k правил поедания пищи следующего вида — если блюдо x съесть непосредственно перед блюдом y (т. е. между x и y не должно быть других блюд), то удовлетворенность Кефы увеличится на c.
Конечно же наш попугай хочет получить максимально возможную удовлетворенность от похода в ресторан. Помогите ему в этом непростом деле!
Выходные данные
В единственной строке выходного файла выведите максимальную удовлетворенность, которую Кефа может получить от похода в ресторан.
Примечание
В первом тесте лучше всего съесть сначала второе блюдо, а потом первое. Тогда мы получим по единице удовлетворенности за каждое блюдо и еще единицу за правило.
Во втором тесте подходят последовательности выбора 4 2 1 или 2 1 4. В обоих случаях мы получим удовлетворенность 7 за отдельные блюда, а также, выполнив правило 1, получаем еще дополнительную удовлетворенность 5.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 1
1 1
2 1 1
|
3
|
|
2
|
4 3 2
1 2 3 4
2 1 5
3 4 2
|
12
|