SP3923 BYTESM2 - Philosophers Stone

One of the secret chambers in Hogwarts is full of philosopher’s stones. The floor of the chamber is covered by h × w square tiles, where there are h rows of tiles from front (first row) to back (last row) and w columns of tiles from left to right. Each tile has 1 to 100 stones on it. Harry has to grab as many philosopher’s stones as possible, subject to the following restrictions: - He starts by choosing any tile in the first row, and collects the philosopher’s stones on that tile. Then, he moves to a tile in the next row, collects the philosopher’s stones on the tile, and so on until he reaches the last row. - When he moves from one tile to a tile in the next row, he can only move to the tile just below it or diagonally to the left or right. Given the values of h and w, and the number of philosopher’s stones on each tile, write a program to compute the maximum possible number of philosopher’s stones Harry can grab in one single trip from the first row to the last row.

The first line consists of a single integer T, the number of test cases. In each of the test cases, the first line has two integers. The first integer h (1

The output should consist of T lines, (1