Problem C: 矩阵取数Ⅲ

Problem C: 矩阵取数Ⅲ

Time Limit: 1 Sec  Memory Limit: 8 MB
Submit: 80  Solved: 14
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有一个m*n的矩阵,每个位置都有一个分数,并且从第二行开始,每个位置的分数都与上一行的分数有关。
具体表达式为:ai,j=ai-1,j*(1+1/m)+i+j
现在PIPI要从矩阵的左上角(1,1)走到右下角(m,n),他每步只能往右或者往下走,
请问他能取得的最大分数是多少?

Input

多组输入。
第一行输入矩阵的大小m和n(1<=m,n<=1000)。
第二行输入n个整数,代表第一行的分数(-1e6<=a1,j<=1e6)。

Output

输出PIPI能获得的最大分数,保留3位小数。

Sample Input

2 3
1 2 3

Sample Output

22.000

HINT

注意内存限制哦,请采用O(N)级别的空间复杂度