HUNTER×HUNTER#10896
In primul volum al popularului manga "Hunter x Hunter", protagonistul Gon si prietenii lui iau parte la Examenul de Vanat. In etapa a patra, fiecare dintre cei participanti numerotati de la 0 la N - 1 primesc cate un ecuson, ecusoanele fiind numerotate tot de la 0 la N - 1. De asemenea, bucati de hartie numerotate de la 0 la N - 1 sunt puse intr-o urna. Fiecare participant extrage cate o bucata de hartie din urna (si nu o pune inapoi); bucata de hartie contine numarul T_{i} reprezentand ID-ul tintei sale. Se garanteaza ca nimeni nu a extras propriul sau numar. Mai exact, T_{i} \neq i pentru oricare .
Dupa aceea, participantii sunt lasati pe insula "Zevil" timp de o saptamana; acolo, acestia isi pot fura ecusoanele unul de la altul. La sfarsitul saptamanii, etapa a patra a examenului se termina, si se noteaza cine este in posesia caror ecusoane. Scorul unui participant este suma punctelor oferite de ecusoanele pe care participantul le poseda la sfarsitul saptamanii. Ecusoanele numerotate cu si T_{i} ofera participantului cate puncte fiecare, iar restul ecusoanelor ofera participantului cate 1 punct fiecare. Participantii care insumeaza cel putin puncte trec cu success etapa, iar restul esueaza.
Evident, este imposibil ca toti participantii sa treaca cu succes de aceasta etapa. Intrebarea ta este care ar fi cel mai bun rezultat, stiind ca tie iti place de anumite caractere mai mult decat de altele. Mai precis, pentru fiecare participant , tu simti L_{i} unitati de atractie pentru acesta (exprimate in unitati de masura care nu conteaza aici). Tu vrei sa calculezi valoarea maxima a sumei tuturor L_{m}-urilor, unde reprezinta ID-urile participantilor care au reusit sa obtina cel putin puncte.
Problema este ca sunt multi participanti, deci si foarte multe combinatii posibile, asa ca iti este greu sa gasesti combinatia cea mai buna. Din fericire, tu traiesti in secolul 21 si ai la dispozitie un calculator modern. Ai decis ca este cel mai bine sa scrii un program hunterxhunter care gaseste valoarea maxima a sumei de mai sus.
De pe prima linie a standard inputului programul vostru trebuie sa citeasca doua numere naturale: si - numarul de participanti si numarul de puncte pe care atat propriul ecuson cat si ecusonul tintei sale le ofera acestuia. De pe urmatoarele linii, programul vostru trebuie sa citeasca cate doua numere naturale: T_{i} si L_{i} - ID-ul tintei participantului si cat de atras esti tu de participantul .
Pe singura linie a standard outputului programul vostru trebuie sa afiseze un singur numar natural: atractia totala maxima posibila pe care o simti pentru participantii care au reusit sa obtina cel putin puncte.
Exemplul 1
Exemplul 2
Participantii care au trecut cu succes de această etapă sunt 1, 4 și 6. O posibilitate este: participantul 1 posedă la final ecusoanele 1 și 6, participantul 4 posedă ecusoanele 0, 4 și 7, iar participantul 6 posedă ecusoanele 2, 3 și 5. Suma atracțiilor este L_1 + L_4 + L_6 = 111 + 105 + 108 = 324.
Pentru a obtine punctele unui subtask, soluția voastră trebuie să treacă toate testele din cadrul subtaskului. Subtaskurile sunt următoarele:
Subtask | Puncte | N | Restrictii aditionale |
1 | 10 | 10 | Niciuna |
2 | 15 | 700 | T_{P_j} = P_{(j+1) \mod N} si L_{P_{N-1}} = 0 |
3 | 15 | 10^4 | T_{P_j} = P_{(j+1) \mod N} si L_{P_{N-1}} = 0 |
4 | 10 | 700 | T_{P_j} = P_{(j+1) \mod N} |
5 | 10 | 10^4 | T_{P_j} = P_{(j+1) \mod N} |
6 | 20 | 700 | Niciuna |
7 | 20 | 10^4 | Niciuna |
Aici, este o permutare arbitrară a numerelor de la 0 la N - 1, cu proprietatea ca P_0 = 0.
Nota: (j + 1) \mod N este restul impărțirii lui (j + 1) la .