cho.shTime limit
5s
Memory limit
128 MB
Hyeongtaek runs a gem shop. The gems are arranged in an N × M grid. Each row has one row lamp that lights the gems in that row, and each column has one column lamp that lights the gems in that column. There are N row lamps and M column lamps in total.
Each gem has a minimum amount of light it must receive to keep its best appearance, and this value can be different for every gem. The following table shows the required light values for gems arranged in a 2 × 3 grid.
| Column lamp 1 | Column lamp 2 | Column lamp 3 | |
|---|---|---|---|
| Row lamp 1 | 2 | 1 | 2 |
| Row lamp 2 | 3 | 1 | 1 |
The light received by the gem at position (i, j) is the sum of the intensity of row lamp i and the intensity of column lamp j. You must choose the intensity of every row lamp and column lamp so that every gem receives at least its required amount of light.
If the column-lamp intensities are 2, 0, 1 and the row-lamp intensities are 1, 1, then the received light values are as follows.
| 2 | 0 | 1 | |
|---|---|---|---|
| 1 | 3 | 1 | 2 |
| 1 | 3 | 1 | 2 |
All gems satisfy their requirements, and the total lamp intensity is 2 + 0 + 1 + 1 + 1 = 5, which is minimal.
Given the required light value of each gem, find the minimum possible sum of intensities of all row lamps and column lamps while satisfying every requirement.
The first line contains two positive integers N and M. Both values are at most 256.
Each of the next N lines contains M positive integers, where each integer is the required light value of one gem. Every given value is at most 2,000,000.
Output the minimum possible total intensity of all row lamps and column lamps while satisfying the requirements.