GARBAGE - Garbage Collection

no tags 

A big office uses a cleaning robot to empty the trash can in every cubicle. The surface of each cubicle is a square and the office floor plan is organized as a rectangular matrix of R rows of C cubicles each. The cleaning process begins by the robot entering the floor by a door that accesses the topmost leftmost cubicle, and finishes with the robot exiting using the same door. Both entering and leaving take 26 seconds each. When the cleaning robot is in a cubicle it can empty the trash can using 13 seconds. The robot can also move to a cubicle that shares a side with its current location, using 38 seconds. The robot needs to enter in each cubicle at least once to empty its trash can.

The total time the robot takes for the entire process depends on the actual tour through the different cubicles. Among all possible tours, we are interested in those of minimum time.

Given the description of the office, you must indicate the minimum time required for the entire cleaning process (including entering, leaving, emptying the trash can in every cubicle, and moving around). Notice that it is possible that an optimal tour passes through a cubicle several times, but the robot has to take the time to empty the trash can only once.

Input

The input contains several test cases, each one described in a single line. The line contains two integers R and C separated by a single space, representing the number of rows and cubicles per row, respectively (1 ≤ R, C ≤ 100). The last line of the input contains the number −1 twice separated by a single space and should not be processed as a test case.

Output

For each test case output a single line with an integer representing the minimum number of seconds that the robot needs to complete the cleaning process.

Example

Input:
4 2
3 3
-1 -1

Output: 460
549

hide comments
N Hari Prasad: 2011-01-31 19:34:34

plz give some bigger test cases please. .

Shaka Shadows: 2010-09-26 19:41:31

Problem PLCNUM1 in the tutorial section can give some good hints about this one :).


Added by:Pablo Ariel Heiber
Date:2010-08-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:FCEyN UBA ICPC Selection 2009