1685--【USACO】Hypnotic Milk Improvement

1685: 【USACO】Hypnotic Milk Improvement


时间限制: 1.000 Sec  内存限制: 64 MB
提交: 7  解决: 2
[提交] [状态] [报告] [命题人:]

题目描述

FJ hires a dairy hypnotist to improve milk production using hypnotic suggestions. FJ knows how much milk each cow currently has for milking (an integer number of liters) and has asked the hypnotist to manipulate the cows to maximize total milk production. FJ has arranged 36 cows on a 6x6 grid. The hypnotist can spin his watch so that it is seen by the six cows in any one row, column, or the major diagonal (upper left to lower right) His power of suggestion can increase or decrease the amount of milk a cow can give by one liter. Of course, if he asks for too much milk (more than 9 liters), the cow gets confused and will give 0 liters. Similarly, a cow asked to reduce from 0 liters will be confused and give 9 liters instead. Below is the arrangement of the milk production for the cows along with the results of hypnotizing cows in various rows and columns:
   Initial        Hypnotize        Hypnotize
 Milk Prod.    Row 1 Increase   Col 1 Decrease
5 9 7 1 5 8      6 0 8 2 6 9      5 0 8 2 6 9
2 5 3 5 2 0      2 5 3 5 2 0      1 5 3 5 2 0
6 8 1 5 0 3  ->  6 8 1 5 0 3  ->  5 8 1 5 0 3
4 8 2 6 9 2      4 8 2 6 9 2      3 8 2 6 9 2
9 1 6 5 3 2      9 1 6 5 3 2      8 1 6 5 3 2
7 0 2 4 3 1      7 0 2 4 3 1      6 0 2 4 3 1
 149 liters       145 liters       139 liters
Using an unlimited number of hypnotic suggestions, maximize the amount of milk that FJ can expect. The moves shown above were surely not optimal!

输入

Six lines each containing six integers which represent the current state of a given cow's milk production. The first line is the uppermost row as illustrated above, and so on.

输出

A single integer which is the largest amount of milk the hypnotist can coax from the cows.

样例

输入  复制
5 9 7 1 5 8 2 5 3 5 2 0 6 8 1 5 0 3 4 8 2 6 9 2 9 1 6 5 3 2 7 0 2 4 3 1
输出  复制
273

来源/分类