Olympiad

Time limit1sMemory limit256 MB

Summary

Given three rectangles with fixed side lengths, arrange them axis-parallel so the union covers the least area, allowing overlaps.

Level: Hard8 of 10
Topics: Geometry, Brute force, Implementation, Math
Solved: No attempts yet

Problem

Gnome-land is preparing for the upcoming Olympiad. The gnome foreman was given the task of building fields for the games of hertball, jordanball, and medveball. Each field is a rectangle. According to the rules of the games, the fields must be placed so that their sides are parallel to the north-south and west-east directions.

Land in Gnome-land is very expensive, so the organizers want to spend as little money as possible on buying the land. Since the hertball, jordanball, and medveball competitions are held at different times, the fields may overlap.

Help the gnomes find the minimum area that the three fields can occupy after they are built.

One possible optimal arrangement of the fields in the first sample is shown in the figure.

Input

The input contains at most 1000 lines, each of which contains a description of three fields: six positive integers, each not exceeding 10000.

The first and second numbers denote the dimensions of the first field, the third and fourth the dimensions of the second field, and the fifth and sixth the dimensions of the third field.

The input ends with a line consisting of six zeros. This query does not need to be processed.

Output

For each set, output a single number: the minimum area that the three fields can occupy.

Examples1

Example 1

Input

2 2 1 3 1 1
4 1 3 2 2 3
5 1 4 2 3 3
0 0 0 0 0 0

Expected output

5
7
12