Little Q is fighting against scary monsters in the game “Monster Hunter”. The battlefield consists of $n$ intersections, labeled by $1,2,…,n$, connected by $n-1$ bidirectional roads. Little Q is now at the $1$-th intersection, with $X$ units of health point(HP).
There is a monster at each intersection except $1$. When Little Q moves to the $k$-th intersection, he must battle with the monster at the $k$-th intersection. During the battle, he will lose $a_i$ units of HP. And when he finally beats the monster, he will be awarded $b_i$ units of HP. Note that when HP becomes negative($<0$), the game will over, so never let this happen. There is no need to have a battle at the same intersection twice because monsters do not have extra life.
When all monsters are cleared, Little Q will win the game. Please write a program to compute the minimum initial HP that can lead to victory.