Rezolvare PBinfo #4407

Mihai s-a decis în sfârșit să compună o melodie. Fără să știe de unde să înceapă, a scris pe o foaie n note muzicale. Fiecare notă muzicală este definită de două valori reprezentând durata și înălțimea acesteia astfel:

• durata este exprimată printr-o fracție de forma \( \frac{1}{{2}^{x}} \), unde x este un număr natural nenul;
• înălțimea este exprimată printr-un număr natural nenul y.

Durata unui grup de note este egală cu suma duratelor notelor din grup. Pentru a compune o melodie corect din punct de vedere muzical, el trebuie să distribuie toate notele în grupuri disjuncte, astfel încât durata fiecărui grup să fie 1. Mihai definește scorul unui grup de note ca fiind suma înălțimilor tuturor notelor din grup, ridicată la pătrat. De asemenea, el definește scorul unei melodii ca fiind suma scorurilor tuturor grupurilor de note formate pentru acea melodie.

Mihai vrea să afle care este scorul maxim al unei melodii pe care îl poate obține după gruparea tuturor notelor date.

Cerința

Dându-se n note sub forma a n perechi de numere, x și y, să se afișeze scorul maxim ce poate fi obținut după gruparea tuturor notelor date în grupuri disjuncte.

Date de intrare

Fișierul de intrare partitura.in conține pe prima linie un număr natural n, reprezentând numărul de note, iar pe următoarele n linii se vor afla câte două numere naturale x și y separate prin câte un spațiu, cu semnificația din enunț, pentru fiecare din cele n note.

Date de ieșire

Fișierul de ieșire partitura.out va conține un singur număr natural reprezentând scorul maxim cerut.

Restricții și precizări

• 1 ≤ n ≤ 300.000
• 1 ≤ x ≤ 18
• 1 ≤ y ≤ 10.000
• Se garantează că se pot distribui toate notele date în grupuri de durată 1.

Exemplul 1:

partitura.in

5
2 3
3 2
2 1
2 2
3 5

partitura.out

169

Explicație

Pentru a determina scorul maxim al unei melodii, singura soluție posibilă se obține prin formarea unui singur grup. Acesta este format din toate notele și are durata \( \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^2} + \frac{1}{2^2} + \frac{1}{2^3} = 1\) și scorul \( {(3 + 2 + 1 + 2 + 5)}^{2} = 169 \). Scorul melodiei este, de asemenea, 169.

Exemplul 2:

partitura.in

6
1 3
2 2
1 4
2 2
2 2
2 2

partitura.out

113

Explicație

Pentru a determina scorul maxim al unei melodii, o soluție posibilă se obține prin formarea a două grupuri.

Primul grup este format din prima, a doua și a patra notă și are durata \( \frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^2} = 1 \) și scorul \( (3 + 2 + 2)^2 = 49 \).

În al doilea grup este format din a treia, a cincea și a șasea notă și are durata \( \frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^2} = 1\) și scorul \( (4+2+2)^2=64 \).

Scorul melodiei este 49 + 64 = 113 și este maximul care se poate obține pentru aceste note.