L'agenda del gran Cthulhu P36784

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

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ó.

0.43

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!

0.55

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 \enspace t_i$ amb el moment de la invocació i el temps que es triga en devorar la víctima. Podeu suposar $1 \le n \le 10^4$, $0 \le m_i \le 10^9$, i $1 \le t_i \le 10^9$.

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.