Minimum Ignition Energy for the Fusion Reactor

The famous inventor SHTSC, known for his part‐assembling machine, has now introduced the Fusion Reactor – a mysterious device that produces a large amount of clean energy. The reactor consists of several fusion blocks connected by links such that:

• Any two blocks can reach each other via some sequence of links.
• The network contains no cycle (i.e. no block can be reached from itself by traversing a series of links without repeating a link).

Each fusion block i requires an initial external energy of \(d_i\) to ignite it. Fortunately, once a block is ignited it automatically sends \(c_i\) units of energy to every directly connected block that has not yet been ignited. These energy transfers may reduce the amount of external energy needed to ignite a block later – indeed, if a block receives energy from one or more of its already‐ignited neighbors then its required external energy is lowered by the total transferred (but not below zero).

The problem is to determine the minimum total external energy needed to eventually ignite every block. In other words, by choosing an optimal order in which to ignite blocks (and letting each ignited block transfer its energy to its unignited neighbors immediately), compute the minimum energy required so that every block becomes ignited.

Explanation: Consider that for each undirected link connecting blocks i and j, you must choose an activation order. If you choose to activate block i before block j, then block j receives an energy transfer of \(c_i\) (and vice‐versa if j is activated first). However, for each block the total energy it can receive cannot exceed its required \(d_i\> (i.e. the transferrable energy is capped by \(d_i\)). Equivalently, one may think of assigning a direction to each link. If an edge \((i, j)\) is assigned from \(i\) to \(j\) (meaning block \(i\) is ignited before block \(j\)), then block \(j\) benefits by \(c_i\) units – but the sum of benefits for block \(j\) is capped by \(d_j\). With an appropriate choice of orientations the total benefit from energy transfers is maximized, thereby minimizing the total external energy needed.

It can be shown that the minimum external energy is

[ \text{Total Energy} = \sum_{i=1}^n d_i - B^* ]

where \(B^*\) is the maximum total benefit achievable by orienting each link under the constraint that the benefit assigned to block \(i\) does not exceed \(d_i\). In this problem, the underlying network of blocks is a tree.

Your task is to compute the minimum total external energy required to ignite all fusion blocks.

inputFormat

The first line contains a single integer \(n\) (\(2 \le n \le 200\)), the number of fusion blocks. The next \(n\) lines each contain two integers \(d_i\) and \(c_i\) (\(1 \le d_i, c_i \le 200\)), representing the external energy required for block \(i\) and the energy it transfers upon ignition, respectively.

The following \(n-1\) lines each contain two integers \(u\) and \(v\) (1-indexed) which indicate that block \(u\) and block \(v\) are directly connected by a link.

outputFormat

Output a single integer – the minimum total external energy required to ignite all fusion blocks.

sample

3
10 5
6 3
8 4
1 2
2 3

16