UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1736. [Usaco2005 jan]The Wedding Juicer 婚宴的榨汁机

Statistics 下载数据

Description

    约翰的奶牛们找到了一份不错的兼职一设计冲压式榨汁机.榨汁机设计如下:
    一个W * H的底座(3≤W,H≤300)
    每一个1 *1的方格上都放有一个高度为B(1≤B≤109)的柱予,用来榨汁.
 假设柱子之间都被完美地粘合了,这样水不会顺着柱子与柱子之间的空隙流走.但是约翰一直不知道,这么一个榨汁机,到底能装多少果汁?假设榨汁机周围没有任何东西,也就是说,边界上的水都会流走,有些榨汁机则根本不能装下任何的果汁.

Input

    第1行:两个整数W和H.
    第2到H+1行:每行W个数字,代表了高度.

Output

 
    最多能装多少毫升的果汁.

Sample Input

4 5
5 8 7 7
5 2 1 5
7 1 7 1
8 9 6 9
9 8 9 9

Sample Output

12

OUTPUT DETAILS:

在两个高1的格子上注入4毫升果汁,到高度5.在高2的格子上注入3毫升果汁,到高度5.在高6的格子上注入1毫升果汁,到高度7.2×4+3+1= 12.

Hint

Source

Gold