在贏得世上所有的資訊競賽後，Peter Hacker開始想要嘗試新的挑戰。因此他在俄羅斯的密碼學線上競賽中以VerhShifr為隊名報名了，並且很快的晉級到了在莫斯科的決賽。

在主辦單位主辦的參訪活動中，他們參觀了俄羅斯娃娃博物館。這個博物館中有非常多奇怪的迷宮。迷宮中都是方型的，而且牆壁都是南北向或東西向。每個展場的四個方向都有個門，博物館的最西北方是入口，最東南方則是出口。

俄羅斯的國手隊準備了有趣的遊戲和他們的對手玩。他們在每間房間放了一個獨特大小的俄羅斯娃娃。每個人必須要走過迷宮，並且收集盡可能多的娃娃，將他們一個一個裝起來。當然參賽者可以決定是否要拿某個房間的娃娃(當然要可以包住你手上最後拿的)或直接繼續往前走。

為了增加難度，一個裁判將每間房間改成只能從東方跟南方出去。Peter當然也對這些限制非常的苦惱。因此他寫了一個可以找到最佳路的程式。

現在請問你是否也能寫出這個程式呢？給你每個房間的娃娃大小，請你寫一個程式去計算最多可以拿到幾個娃娃。

After wining every informatics competition in the world, Peter the Hacker decided to try a different type of challenge. He registered in the Russian web site for online competitions in cryptography and locksmith “VerhShifr” and soon he has arrived in Moscow, participating in the finals.
During one of the excursions that the organizers prepared, the group visited a large museum for Matryoshka dolls – traditional Russian nested toys. Inside the museum, there was a strange labyrinth. Its rooms and the labyrinth itself were squares and their walls were parallel to the north-south and east-west axes. Each chamber had four doors – one on each side. The entrance to the labyrinth was in the most northwestern room and the exit – in the most southeastern.
The Russian national team in ciphers prepared an interesting game for their opponents. In each room, they left a single empty Matryoshka doll with unique size. Everyone had to go through the labyrinth and collect as many toys as possible but under one condition. Every time someone picks a doll, he has to nest all the dolls he has into the new one. Of course, the contestants could decide whether to pick a Matryoshka (if it is bigger than the last one) or to continue to the next room. To make things even harder, the genius of the safes – Metr Pitrichev – had modified the doors so that from a room one can move only to the rooms to the south and to the east.
Peter, of course, was not such a master with the locks and could not deal with the modification. Instead, he wrote a program, which can find the best way to collect as many toys as possible. Can you do that, too? Write a program matr that calculates the maximum amount of Matryoshka dolls, which Peter the Hacker can collect for a given configuration of rooms.