问题 C: 带权路径计数

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:3 解决:2

题目描述

给定一个 n×m 的网格,每个格子 (i,j) 上有一个非负整数 wi,j,表示经过该格子需要付出的代价。一个人从左上角 (1,1) 出发,只能向右或向下移动,到达右下角 (n,m)。

现在定义一条路径的代价为该路径上所有格子(包括起点和终点)的权值之和。请你求出所有路径中代价的最小值,以及在最小代价下的路径条数。

注意:如果存在多条路径达到最小代价,需要输出这些路径的条数。

输入

  • 第一行两个整数 n,m(1≤n,m≤100)。

  • 接下来 n 行,每行 m 个整数,表示每个格子的权值 wi,j(0≤wi,j≤100)。

输出

输出两个整数,分别表示最小代价和对应的路径条数(用空格分隔)。

样例输入 复制

3 3
1 3 1
1 5 1
4 2 1

样例输出 复制

7 1

提示

1≤n,m≤100

 0 ≤ w i , j ≤ 100 

0≤w i,j ≤100