SP3923 BYTESM2 - Philosophers Stone

卡塞尔的一个密室里装满了贤者之石。房间地面铺有h×w方砖，从前(第一排)到后(最后一排)有h排砖，从左到右有w列砖。每块瓷砖上有1到100块石头。路明非必须抓住尽可能多的贤者之石，但有以下限制:他从选择第一行的任何一块砖开始，然后在那块砖上收集装备部的石头。然后，他移动到下一行的一个瓦片上，在瓦片上收集装备部的石头，如此类推，直到他到达最后一行。当他从一个瓦片移动到下一行的瓦片时，他只能移动到它下面的瓦片或向左或向右对角移动。给定h和w的值，以及每块磁砖上的贤者之石的数量，编写一个程序来计算路明非从第一行到最后一行的一次行程中可以获得的贤者之石的最大可能数量。

- 第一行包含一个整数T，即测试用例的数量。在每个测试用例中，第一行都有两个整数。 - 第一个整数h (1

- 输出应该由T行组成(1