Statement

A group of mountaineers are planning an expedition to the top of Mont Blanc, the highest mountain in the Alps. Some areas of the mountain can be traversed by walking, but others are so steep that they require the use of ladders. They already mapped out the mountain and modeled it as an N × M grid. Each cell (i, j) has an elevation H_i,j. The mountain climbers start at (1, 1) and want to reach the summit at (N, M). They can only move to adjacent cells (up, down, left, right). Normally, they can only move to an adjacent cell if they are strong enough. More precisely, if the absolute difference in elevation between the current cell and the target cell is not greater than D. However, they can bring at most K ladders with them. Using one ladder allows them to completely ignore the elevation difference for a single move. The climbers want to know how strong they need to be for the expedition...