Picky children#671
The nanny is putting the children to sleep, but she cannot rest herself: as soon as she settles some in bed, others wake up...
The nanny has children, each with a different sleep pattern. She knows how many minutes it takes to put the -th child to sleep (denoted by a_k), and how many minutes the child will stay asleep afterwards (denoted by b_k). The nanny can only sleep when all the children are asleep at the same time.
Help the nanny find the order in which to put the children to bed so that she can maximize the length of her continuous sleep.
For example, suppose there are children: a_1=1, b_1=10, a_2=10, b_2=20. If she starts with the first child, it will take her minutes to put the second to bed, and during this time the first will wake up. If she starts with the second child, she will then have time to put the first child to bed and get a full minutes of rest.
The first line contains (1 \leq N \leq 100000). The second line contains natural numbers a_1, \dots, a_N, and the third line contains b_1, \dots, b_N. The numbers do not exceed 10^9 and are separated by spaces.
Output a single integer — the maximum possible time the nanny can sleep, or if it is not possible for her to rest at all.
Example 1