题目描述

这一天，Hnsdfz 信息组的众人决定上岳麓山玩。岳麓山上的可以探险的地方非常多，而信息组的 Oier 们給每一个地方都设定了一个危险值，代表探险这个景点需要承担的危险，而整个岳麓山可以抽象为由 $n$ 行数字组成的数字梯形。而梯形顶端有 $m$ 个数字，在每个数字处可以往左上或右上移动，形成一条从梯形底至顶的路径。

而一开始，每个人都觉得如果走过别人走过的地方就太没个性了。于是有

任务一: 找出 $m$ 条完全不相交的至底至顶的路径。

但略一思考，又都觉得如果限定这么死，那就太无趣了，于是有:

任务二: 找出 $m$ 条仅在数字处相交的路径。

现在，做为整个浏览计划的发起者，你要计算出对于任务一与任务二，每个人观赏线路所能经受的最小危险。

输入格式

第一行两个正整数 $n$，$m$。表示整个梯形有 $n$ 行，第一行有 $m$ 个列。

接下来 $n$ 行描述整个数字梯形。第 $i$ 行有 $n+i-1$ 个数字。

输出格式

分两行输出，分别是对应任务一与任务二的结果。

样例输入

3 2
1 2
2 1 2
2 2 2 2

样例输出

10 
9

样例解释

第 $i$ 个数字表示每条路线在第 $i$ 行走第几个数字。

任务一的两条路线 $1 \to 1 \to 1$；$2 \to 2 \to 2$；

任务二的两条路线 $1 \to 2 \to 1$；$2 \to 2 \to 2$；

数据规模及约定

对于 $10 \%$ 的数据 $n\le 10$； $m\le 5$；

对于 $100 \%$ 的数据 $n\le 80$； $m\le 80$；对于每个数字 $num$， 保证 $num \le 20$；

题目来源

HNOI2009 集训 Day4