L'agenda del gran Cthulhu P36784

Statement

thehtml

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 m_i ⁠ ⁠ t_i amb el moment de la invocació i el temps que es triga en devorar la víctima. Podeu suposar 1 ≤ n ≤ 10⁴, 0 ≤ m_i ≤ 10⁹, i 1 ≤ t_i ≤ 10⁹.

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++