Angel Relief

Time Limit : 1 sec, Memory Limit : 262144 KB

K: 救済 (Angel Relief)

天使の天真さんは、ある街を救うことにした。

この街は南北 $H$ 区画 × 東西 $W$ 区画に分けられた長方形の形をしており、各区画に家がある。

北から数えて $X$ 番目、西から数えて $Y$ 番目の区画を $(X, Y)$ で表す。

区画 $(i, j)$ にある家には $A_{i, j}$ 人の人が住んでいる。

天真さんは、辺が南北または東西に平行または垂直な長方形のエリアを選び、その中に住んでいる人全員をひとりずつ救済する。

天真さんは、考えられるすべての長方形でこの操作を行う。

天真さんが人を救済する回数の合計を求めよ。

入力

1 行目に、整数 $H, W$ が空白区切りで与えられる。

続く $H$ 行のうち $i$ 行目には、整数 $A_{i, 1}, A_{i, 2}, A_{i, 3}, \dots, A_{i, W}$ が空白区切りで与えられる。

出力

天真さんが人を救済する回数の合計を出力せよ。

制約

  • $H, W$ は $1$ 以上 $500$ 以下の整数
  • $A_{i, j}$ はすべて $1$ 以上 $9$ 以下の整数である。

入力例1

2 2
1 2
4 8

出力例1

60

例えば、左上を $(1, 1)$、右下を $(2, 2)$ となるように長方形のエリアを選ぶと、そこにいる $15$ 人をひとりずつ救済するので、合計 $15$ 回の救済を行う。

$9$ 通りの長方形のエリアに対して、それぞれ $1, 2, 3, 4, 5, 8, 10, 12, 15$ 回の救済を行うので、合計で $60$ 回である。

入力例2

2 3
1 2 3
4 5 6

出力例2

140