天使の天真さんは、ある街を救うことにした。
この街は南北 $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}$ が空白区切りで与えられる。
天真さんが人を救済する回数の合計を出力せよ。
2 2 1 2 4 8
60
例えば、左上を $(1, 1)$、右下を $(2, 2)$ となるように長方形のエリアを選ぶと、そこにいる $15$ 人をひとりずつ救済するので、合計 $15$ 回の救済を行う。
$9$ 通りの長方形のエリアに対して、それぞれ $1, 2, 3, 4, 5, 8, 10, 12, 15$ 回の救済を行うので、合計で $60$ 回である。
2 3 1 2 3 4 5 6
140