{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"Элронд созвал военный совет. На столе в зале заседаний Военного совета лежит прямоугольная карта Мордора в сетке N x M. В каждой ячейке сетки указано количество орков в ней. В верхнем левом углу игрового поля изображена Роковая гора, а в правом нижнем углу — запланированная точка входа Фродо в Мордор. Путь Фродо через Мордор соответствует движению по карте, начиная с правой нижней клетки и продвигаясь через соседние квадраты к правой верхней клетке. (т.е. может перемещаться из любой клетки в 4 соседние клетки. Невозможно перемещаться по диагонали)\n\nЕсли бы Фродо занимал определенную клетку, он привлекал бы внимание всех орков в этой камере. Помогите Элронду рассчитать минимальное количество орков, необходимое Фродо, чтобы добраться до места назначения — Роковой горы.\n\n"}},{"title":"Input","value":{"format":"HTML","content":"Входной файл состоит из множества карт. В первой строке записано целое число k, обозначающее количество карт. Следующие две строки содержат целые числа N и M, определяющие размер карты. Количество орков в каждой ячейке затем указывается в следующих N строках в виде матрицы NxM. После этого аналогично делаются данные для следующей карты.\n"}},{"title":"Output","value":{"format":"HTML","content":"Для каждой карты выведите минимальное количество орков, с которыми можно столкнуться на этой карте. Убедитесь, что ответы на разных картах находятся на разных линиях."}},{"title":"Constraints","value":{"format":"HTML","content":"1 ≤ количство карт k ≤ 100 \u003cbr\u003e\n0 ≤ количество орков в каждой ячейке на любой заданной карте ≤ 9 \u003cbr\u003e\nколичество ячеек на карте (т. е. размер карты) ≤ 999 x 999\n"}},{"title":"Sample Input ","value":{"format":"HTML","content":"2 \u003cbr\u003e\n4 \u003cbr\u003e\n5 \u003cbr\u003e\n0 3 1 2 9 \u003cbr\u003e\n7 3 4 9 9 \u003cbr\u003e\n1 7 5 5 3 \u003cbr\u003e\n2 3 4 2 5 \u003cbr\u003e\n1 \u003cbr\u003e\n6 \u003cbr\u003e\n0 1 2 3 4 5 \u003cbr\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"24 \u003cbr\u003e\n15"}}]}