K специальных ячеек
Вам дана матрица, в которой выделены специальных ячеек. Вы должны достичь клетку из . Из любой клетки можно двигаться только вправо или вниз.
специальных ячеек — это те ячейки сетки, которые обладают особой силой. -я специальная ячейка имеет единиц силы, и если Вы проходите по этой ячейке, то приобретаете эту силу.
Найдите общую суммарную силу, которую Вы можете приобрести после прохождения всех возможных путей в сетке, чтобы достичь ячейки .
Отметим, что:
Сила пути равна сумме сил всех специальных ячеек, посещенных на этом пути.
Ячейки, не являющиеся специальными, имеют силу ноль.
Giriş verilənləri
Первая строка содержит количество тестов .
Первая строка каждого теста содержит три целых числа и , где — размер сетки, а — общее количество специальных ячеек в сетке. Каждая из следующих строк содержит и , где — расположение специальной ячейки, а — ее сила.
Çıxış verilənləri
Для каждого теста выведите в отдельной строке общую силу, которую Вы можете приобрести. Поскольку общая сила может быть слишком большой, то выведите ее по модулю .