A Knight some Trolls and a Princess - A possible new problem

This paragraph is best read after the problem description. The example given below is much smaller than the intended size of the problem. I have worked with the value of N randomly chosen in the range 9 to 14 and then set the value of M to be 46 - N. Each of the troll charges are then chosen randomly to be in the range 100 to 999. I have created code which sets a problem and also provides the correct solution. Run time is negligible.

The following is a draft problem description:

King Verence commissioned the knight Sir Galahad to rescue his daughter who is being held prisoner in a castle in the Southern Kingdom. To reach the Southern kingdom Galahad has to pass from north to south through the land of the trolls. This land is bounded to the east and west by precipitous cliffs. Trolls are anti-social beings who live in isolation within their own area of land. These areas are adjacent to each other with no additional land in between. The trolls have gates in the northern and southern edges of their land to allow for the passage of travellers. This allows the trolls to charge a toll whenever someone crosses their land.

The troll land areas are all equal-sized rectangles arranged neatly in east-west rows. The whole area gets progressively wider as we move southwards. This means that each row has one more troll than the previous row. The following example should make this clear but the actual problem will be considerably bigger. Galahad has obtained a map of the troll lands. This is shown below.

          295 174 252 226 982
        353 992 690 282 707 678
      303 771 388 189 782 331 234
    887 959 222 254 222 914 136 221
  198 635 206 884 480 249 179 900 149
573 610 694 705 894 691 677 563 226 255

The land area of each troll is marked by a number, which is also the cost of crossing that troll's land. When moving through the troll lands Galahad can only move southwards (there are no gates in the east/west boundaries). From each troll land he can move into either of the two troll lands to the south. For example, if he enters the troll lands from the north via the troll land second from the left (cost 174 silver pieces) he will be able to proceed to either of two troll lands in the next row (costs 992 and 690). Clearly Galahad wants to minimise the total cost of his journey through the troll lands. Unknown to the trolls, he has been given a magic amulet (which can only be used once). This allows him to travel east or west so that he can travel unseen between any two troll lands in the same row, without incurring an additional charge.

Galahad will eventually need to give his expense account to King Verence. Since the king has no way of knowing what route was taken through the troll lands Galahad thinks that he might claim significantly more than he actually pays. To judge how much he can get away with he decides to work out what would be the maximum cost of travelling through the troll lands. (He will then choose something between the maximum and minimum for his claim.) You are required to calculate these minimum and maximum costs of travelling through the troll lands. Using the example above, the minimum cost is 1293 silver pieces by following the path through 226, 282, 189, amulet transfer east to 234 (no charge) on the same row, then through 221, 149 and 226. The maximum cost is 5163 silver pieces for the path through 982, 707, 782, 914, amulet transfer west to 254, then through 884 and 894.

There is no need to consider the return journey. Trolls are very fond of princesses so passage through their land for the princess and her escort is free.

The first line of the problem contains two space-separated integers, N and M. N is the number of trolls in the first row. M is the number of rows of trolls. Each row contains the cost charged by each of the trolls in that row, for crossing their land. So the first row contains N space-separated values, the second row contains N+1 values and finally row M of the trolls contains N+M-1 values. Your answer should be the minimum cost followed by a space and then the maximum cost.

Example:

input:
5 6
295 174 252 226 982
353 992 690 282 707 678
303 771 388 189 782 331 234
887 959 222 254 222 914 136 221
198 635 206 884 480 249 179 900 149
573 610 694 705 894 691 677 563 226 255

answer:
1293 5163

Rodion, Hi

Once again you have put a problem in place much faster than I had expected. I really like the photo of the trolls. My daughter had a very similar collection. There is definitely no need to replace it with anything else!