L'agenda del gran Cthulhu P36784


Statement
 

pdf   zip

html

Els membres del “Ultimate Programmers Cult” (UPC) han descobert una manera d’obtenir un AC en els concursos de programació: Es pot invocar el gran Cthulhu mitjançant

Ph’nglui mglw’nafh Cthulhu R’lyeh wgah’nagl fhtagn!
Ia! Ia! Cthulhu fhtagn!

Si Cthulhu apareix, devora un membre de l’equip, però a canvi s’obté un AC instantàniament. Per això, molts participants de l’últim SWERC han provat sort amb la invocació.



Malgrat l’immens poder del gran Cthulhu, necessita una estona, potser diferent, per devorar cada víctima. Cthulhu no fa cas de cap crida mentre està menjant. A més, Cthulhu pot ignorar totes les crides que vulgui.

Com que probablement ja sou bons seguidors del culte al gran Cthulhu, us demanem que organitzeu la seva agenda. L’objectiu és maximitzar el temps total que estarà menjant. Heu de fer-ho bé, o sereu objecte de la seva ira... Ia! Ia! Cthulhu fhtagn!

Entrada

L’entrada consisteix en diversos casos, només amb nombres enters. Cada cas comença amb el nombre de crides n, seguit de n parells mi   ti amb el moment de la invocació i el temps que es triga en devorar la víctima. Podeu suposar 1 ≤ n ≤ 104, 0 ≤ mi ≤ 109, i 1 ≤ ti ≤ 109.

Sortida

Per a cada cas, si es poden atendre totes les crides, escriviu “Cthulhu fhtagn!”. Altrament, escriviu el màxim temps total que Cthulhu pot estar menjant.

Public test cases

  • Input

    3
2 3  3 6  8 5
2
4 1  5 10
2
4 2  5 10
7
3 4  2 2  1 2  4 6  7 3  7 2  7 3
3
0 1000000000  0 1000000000  0 1000000000

    Output

    8
Cthulhu fhtagn!
10
9
1000000000
    • Information
    Author
    Enrique Jiménez
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++