Training for the World Finals P51803


Statement
 

pdf   zip

html

The UPC team 12 seconds could barely train for the World Finals. For instance, sometimes only Ferran and Ángel could join for a training. In those cases, a possible strategy was to make Ferran think about how to solve the problems, and to make Ángel program the solutions previously found and written down on paper by Ferran.

Supose that a training had n problems. Let ti be the time that Ferran needed to solve the i-th problem, and pi be the time that Ángel needed to program the i-th problem. Both Ferran and Ángel could only perform one task at a time, but could decide the order of thinking and the order of programming, with just one restriction: Ferran had to completely solve a problem before Ángel could start programming its solution.

Given all this information, can you please minimize the total time to solve and program all the problems?

Input

Input consists of several cases, each one with n followed by t1, …, tn, followed by p1, …, pn. Assume 1 ≤ n ≤ 105, and that all ti and pi are between 1 and 109.

Output

For every case, print the minimum time to solve and program all the problems.

Public test cases
  • Input

    2
    80 90
    100 100
    
    4
    4 4 4 4
    1 2 4 6
    
    5
    5 1 2 3 6
    3 1 3 5 5
    
    3
    1000000000 1000000000 1000000000
    1000000000 1000000000 1000000000
    

    Output

    280
    17
    20
    4000000000
    
  • Information
    Author
    Ferran Alet and Ángel García
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Setzè Concurs de Programació de la UPC - Semifinal
    Date
    2018-06-20