In this game, the rocky grid has K layers and each layer has N gems with hardness value ranging from 1 to 9. If a stone in any layer is broken by hammering, then all the corresponding gems of all layers will automatically break by magic.
You can start breaking gems from any layer initially and can switch to any other layers but once switched you will not be able to return back to previous layer. There is a dragon behind the grid and his life is associated with each layer of grid, so you need to break atleast one stone from each layer to kill the dragon.
Note:
- If you break a stone on ith
position on layer a, then the gems on ith position of all the layers will be broken. - You have to break all the gems of all the layers, either magically or by breaking the gems.
- If you are on layer a and you broke stone on the ith postion, and you are switching to layer b you can’t move to ith position again in layer b. As all the gems lying on the ith position on all the layers are already broken.
- You have to break at least one stone in each of the layer.
Energy required to break the stone of hardness say ‘a’ is ‘a’ calories itself.
Find the minimum energy required to break whole grid and killing the dragon.
Input:
Given N number of gems in each layer and K number of layers of grid.
Next K lines contain N values corresponding to hardness values of each layer.
Output:
Output the minimum energy required.
Constraints:
1 <= N <= 100000
1 <= K <= 5
1 <= hardness value <= 9
SAMPLE INPUT
5 3
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
SAMPLE OUTPUT
8
Explanation
Break stone-1,2,3 from layer-1 and then break stone-4 from layer-2 and stone-5 from layer-3
Total Energy required = 1 + 1 + 1 + 2 + 3 = 8