Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Jei norite pateikti savo sprendimą - prisijunkite.

Olimpiada

Artėja tarpgalaktinė tarpdalykinė super olimpiada! Olimpiadoje yra m skirtingų dalykų, tarp kurių dalyviai gali rinktis.Treneris Tadeušas nori išsiųsti moksleivių komandą į šią olimpiadą, tačiau visų pirma tą komandą reikia suformuoti.

Mokykloje yra n vaikų, norinčių dalyvauti. i-tasis iš jų gerai išmano s_i-ąjį dalyką, o jo išmanymo lygis yra r_i (šis lygis gali būti ir neigiamas!).

Olimpiados taisyklėse parašyta, kad kiekviena mokykla turi išsirinkti tam tikrą poaibį dalykų, kuriuose nori rungtis. Vienintelis ribojimas - moksleivių, dalyvaujančių tam tikrame dalyke, skaičius turi būti vienodas visiems dalykams, kuriuose mokykla nusprendė dalyvauti. Pavyzdžiui, jei mokykla turi du vaikus, kurie išmano matematiką, tris vaikus, kurie išmano informatiką, ir keturis vaikus, kurie išmano fiziką, tai mokykla galėtų siųsti tokias sudėtis:

  • Po 1 vaiką į matematiką, informatiką ir fiziką
  • Po 2 vaikus į matematiką, informatiką ir fiziką
  • Po 2 vaikus į matematiką ir informatiką
  • Tris vaikus į fiziką
  • Ir t.t.
Deja, mokykla negalėtų siųsti vieno vaiko į matematiką ir dviejų į informatiką, nes kiekvienam dalykui siunčiamų vaikų skaičius turi būti vienodas.

Akivaizdu, kad treneris Tadeušas nori, kad jo mokyklos komanda pasirodytų kuo geriau. Jis sugalvojo strategiją: kiekvienas jo siunčiamas moksleivis dalyvaus tik tame dalyke, kurį jis išmano. Treneriui iškilo klausimas - kuriuos mokinius reiktų rinktis, bendras dalykų išmanymas komandoje būtų maksimalus? Jei kiekvienai komandai, kurią įmanoma surinkti, bendras dalykų išmanymo lygis yra neigiamas, treneris Tadeušas bus liūdnas ir nuspręs olimpiadoje išvis nedalyvauti.

Pradiniai duomenys

Pirmoje eilutėje įvesti du tarpais atskirti sveikieji skaičiai n ir m - atitinkamai moksleivių ir dalykų kiekis (1\\leqn,m\\leq10^5).

Kiekvienoje iš sekančių n eilučių yra po du sveikuosius skaičius s_i ir r_i - i-ojo moksleivio išmanomo dalyko numeris ir to dalyko išmanymo lygis (1\\leqs_i\\leqm,-10^5\\leqr_i\\leq10^5).

Rezultatai

Jūsų programa turi išvesti vieną sveikąjį skaičių - didžiausią galimą bendrą dalykų išmanymo lygį sudarytoje komandoje. Jei olimpiadoje bus nuspręsta nedalyvauti, išveskite 0.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
6 3
2 6
3 6
2 5
3 5
1 9
3 1
 
22
 Optimalu rinktis 1, 2, 3 ir 4 moksleivius - du iš jų dalyvaus 2 dalyko varžybose, o kiti du - trečio dalyko. Bendras išmanymo lygis: 22. 
5 3
2 6
3 6
2 5
3 5
1 11
 
23
 Optimalu rinktis 1, 2 ir 5 moksleivius, kurie dalyvaus skirtingų dalykų varžybose. Bendras išmanymo lygis: 23. 
5 2
1 -1
1 -5
2 -1
2 -1
1 -10
 
0
 Kad ir kokią komandą sudarytų treneris, išmanymo lygis visada bus neigiamas, tad olimpiadoje bus nuspręsta nedalyvauti.