探险计划

Hnsdfz 信息组的同学们决定前往岳麓山游玩。岳麓山上有许多可供探险的地点，信息组的 OI 选手为每个地点设定了一个危险值，表示探索该地点需要承担的危险。整个岳麓山可以抽象为一个由 $n$ 行数字组成的数字梯形，其中梯形顶端的第 $1$ 行有 $m$ 个数字。

设第 $i$ 行第 $j$ 个数字的危险值为 $a[i][j]$。一条路径依次选择位置 $p_1,p_2,\ldots,p_n$，其中 $1\le p_i\le m+i-1$，且满足 $p_{i+1}=p_i$ 或 $p_{i+1}=p_i+1$。也就是说，从顶行向底行移动时，每一步只能到达下一行的同列位置或下一列位置；反向行走与此等价。

一条路径的危险值为

$$\sum_{i=1}^{n}a[i][p_i]。$$

一个方案由 $m$ 条路径组成，其总危险值为这 $m$ 条路径的危险值之和。如果多条路径经过同一个数字，则该数字的危险值会对每条经过它的路径分别计算一次。

需要完成以下两个任务：

• 任务一：选择 $m$ 条路径，任意两条路径不能经过同一个数字。
• 任务二：选择 $m$ 条路径，任意两条路径不能使用相邻两行之间的同一条连接边，但可以经过同一个数字，包括共享顶行起点或底行终点。$m$ 条路径不必从顶行的 $m$ 个不同数字出发。

请分别求出任务一和任务二中，方案总危险值的最小值。

输入格式

第一行包含两个正整数 $n,m$，表示数字梯形共有 $n$ 行，且第 $1$ 行有 $m$ 个数字。

接下来 $n$ 行描述数字梯形。第 $i$ 行包含 $m+i-1$ 个整数，依次表示该行从左到右各个数字的危险值。

输出格式

输出两行。

第一行输出任务一的最小总危险值。

第二行输出任务二的最小总危险值。

样例输入

3 2
1 2
2 1 2
2 2 2 2

样例输出

10
9

样例解释

使用一个数字序列表示一条路径，其中第 $i$ 个数字表示该路径在第 $i$ 行选择的位置。

任务一中，可以选择路径 $1,1,1$ 和路径 $2,2,2$，总危险值为 $10$。

任务二中，可以选择路径 $1,1,1$ 和路径 $1,2,2$，总危险值为 $9$。

数据范围

• 对于 $10\%$ 的数据，$n\le 10$，$m\le 5$；
• 对于 $100\%$ 的数据，$n\le 80$，$m\le 80$；
• $a[i][j]$ 为整数，且 $0\le a[i][j]\le 100$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

3 2
1 2
2 1 2
2 2 2 2

输出

10
9