Source: Interview

There is grid 'a' of size n*m. There is a guy on cell (1,1) and he wants to reach (n,m). He can move either down or right. Initially, he has health H. If he gets on cell (i,j), then a[i][j] is added to his health. If his health becomes less than or equal to 0, he dies.

Find the minimum value of H so that he can reach the cell (n,m).

I told her binary search but she asked to remove log factor.

How to solve this?