AIOC Banner

Problem: Mobile Construction Set

Want to try solving this problem? You can submit your code online if you log in or register.


Mobile Construction Set

Time Limit: 3 seconds
Memory Limit: 10 Mb

Your younger sister just got a mobile construction set for her birthday. The set consists of two different kinds of elements: rods and decorations, as illustrated below.

Each rod has three hooks attached via pieces of string. In the middle of each rod, a string rises upwards with a hook at the top. This allows the entire rod to be hung beneath some other object (either the ceiling or a higher decoration). One and only one rod must attach the mobile to the ceiling. At the ends of each rod, strings fall down with hooks at the bottom. This allows a decoration to be hung beneath the rod at each end.

There are many types of decorations, with differing shapes and weights. Each decoration has two rings attached to it, one at the top and one at the bottom. The top ring can be used to hang the decoration on a hook beneath the left or right end of a rod. The bottom ring can be used to hang another rod beneath the decoration.

When building a mobile with this set, no hook may be left free except for the very top hook that hangs the entire mobile from the ceiling. Every other hook must be attached to a decoration. Decorations are not so constrained; some decorations may have other rods hanging beneath them, whereas other decorations may have nothing attached to their bottom ring. An example of a completed mobile is illustrated below. The rods are numbered from 1 to 7, and the weight of each decoration is written beside it.

Your younger sister has finished making a beautiful mobile with her set, but she is complaining that it doesn't work! Indeed, the mobile is far from being well balanced: what is hanging on one side of a rod is sometimes much heavier than what is hanging on the other side.

You have offered your help, but your sister gets upset when you explain that you will have to move some things around. She doesn't want you to change anything in her beautiful construction — it's perfect the way it is, you just have to make it work! You manage to convince her that you need to change at least something to improve the balance, but she will only allow you to make a single change to her creation.

Your task is to make the entire mobile as balanced as possible, by making only one modification to it. This modification must involve detaching a rod from the decoration under which it is hanging, and then reattaching it beneath some other decoration. You don't need to worry about whether different parts of the mobile might bump into each other, since you can always fix this afterwards by changing the lengths of some strings. Making the mobile balanced is your only concern.

To measure how balanced a rod is, you must calculate the absolute value of the difference between the total weights hanging from each end (so a lower number is better). To measure how balanced the entire mobile is, you must add up these differences for every rod. Your goal is to reduce this total to its smallest possible value by making at most one change. Note that you are not required to make a change; you may choose to move nothing at all.

Note also that when moving a rod, you may not attach the rod to a decoration that already has another rod hanging from it. Rods, strings and hooks are so light that they can be considered as having no weight at all.

Constraints

Furthermore, for 30% of the available marks, N <= 200.

Input

The first line of input contains one integer: N, the number of rods used in the mobile. The rods are numbered from 1 to N, with rod 1 being attached to the ceiling.

Each of the following N lines describes a rod. These rods are given in order from 1 to N (so that the second input line describes rod 1, the third input line describes rod 2 and so on). Each of these lines is of the form W1 R1 W2 R2, where W1 and W2 are the weights of the decorations attached directly beneath the left and right ends of the rod, and R1 and R2 are the numbers of the rods hanging beneath these decorations (where rods R1 and R2 hang beneath the decorations of weight W1 and W2 respectively). If a decoration has no rod hanging beneath it, the corresponding rod number will be zero.

Output

The output should contain one line, with a single integer: the minimum sum of weight differences that you can get by moving at most one rod of the mobile.

Sample Input

The following input scenario describes the large mobile illustrated earlier.

7
4 2 20 3
12 4 4 5
12 6 20 7
3 0 3 0
6 0 6 0
6 0 6 0
7 0 7 0

Sample Output

42

In the input scenario, the weight differences for rods 1,...,7 are 40, 2, 10, 0, 0, 0 and 0 respectively, coming to a total sum of 52. By moving rod 7 so that it hangs beneath one of the decorations attached to rod 5, these weight differences become 12, 12, 4, 0, 14, 0 and 0, coming to a total sum of 42. No smaller total sum can be obtained without moving more than one rod, and so 42 is the final answer.

Scoring

The score for each input scenario will be 100% if the correct answer is output, and 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 15 November 2019,  5:40am AEDT