Hide

Problem D
Nafnatalning

Languages en is
/problems/nafnatalning/file/statement/is/img-0001.jpg
Ónefndu tvíburarnir (mynd fengin af pexels.com)
Sunna og Ari er nýbúin að eignast tvíbura. Þau eiga hins vegar eftir að ákveða hvað tvíburarnir eiga að heita. Til þess að geta greint á milli tvíburanna vilja þau ekki að þeir hafi nöfn með sama uppruna, því eins og er geta þau ekki greint á milli tvíburanna. Þau eru búin að finna $n$ uppruna sem þau hafa áhuga á og hafa valið $a_i$ nöfn fyrir upprunann $i$.

Það er stutt í skírnina, bara 42 dagar! Þau þurfa ákveða hvað þau ætla að skíra tvíburana fyrir skírnina. Á hverjum degi geta þau skoðað $P$ pör af nöfnum. Þau hafa beðið þig um að ákvarða hversu marga daga það mun taka að skoða öll nafnapörin.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $2 \leq n \leq 10^6$ og $1 \leq P \leq 10^9$ í þessari röð. Síðan kemur ein lína með $n$ heiltölum þar sem $i$-ta línan er heiltalan $0 \leq a_i \leq 1000$.

Úttak

Skrifið út hvað það tekur marga daga fyrir Sunnu og Ara að skoða öll nöfnin.

Stigagjöf

Hópur

Stig

Takmarkanir

1

50

$2 \leq n \leq 10^3, 0 \leq a_i \leq 10$

2

50

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
2 5
2 3
2
Sample Input 2 Sample Output 2
10 5
1 1 1 1 1 1 1 1 1 1
9