|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||1924||787||627||42.653%|
There are pizza boxes all of which have the same dimensions. The boxes are stacked in piles, forming a three- dimensional grid where the heights are all different. The view from front shows the height of the tallest pile in each column, the view from the side shows the height of the tallest pile in each row.
What is the maximum number of pizza boxes we can remove without changing the front and side views? In the following example, Figure I.2 shows the solution of Figure I.1(a) case. In Figure I.1(a) and Figure I.2, each number (height) represents the number of boxes stacked.
Figure I.1. (a) Grid of heights and (b) the corresponding views.
Figure I.2. Grid of heights after removing boxes.
Your task is to compute the maximum number of pizza boxes that can be removed without changing the original front and side views.
Your program is to read from standard input. The input contains two integers, n and m (1 ≤ n, m ≤ 1,000), the number of rows and columns in the grid, respectively. Each of the following n lines contain m integers, the number of pizza boxes (heights) in the corresponding row. All heights are between 0 and 109 inclusive and the heights are all different.
Your program is to write to standard output. Print exactly one line for the input. The line should contain the maximum number of pizza boxes that can be removed without changing the original views.
4 4 1 2 4 6 16 9 13 11 5 10 8 15 12 14 7 3
3 5 1 11 25 20 23 17 2 16 21 15 10 3 12 24 22