Help Me Friends Plzzz

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.


  1. If you break a stone on ith
    position on layer a, then the gems on ith position of all the layers will be broken.
  2. You have to break all the gems of all the layers, either magically or by breaking the gems.
  3. 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.
  4. 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.


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 the minimum energy required.

1 <= N <= 100000
1 <= K <= 5
1 <= hardness value <= 9


5 3

1 1 1 1 1

2 2 2 2 2

3 3 3 3 3




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

Can you explain that why did you not choose all 1’s from 1st layer?

we have to break 1 gems at least from 1 layer

Do we need to break gems in order? That is if we are at level i, breaking gem j, then next gem that can broken in level i has to be (j+1)?

Please provide the actual link of that question. It’s still unclear to me…

its my assignment not a web link

you can break i+1th layers minimum cost gems and it can be j+1,j+2/… but not j…bcoz the column already broken by breaking j gems og ith layer and you have to break atleast 1 gems in each layer