Matbeställning

문제

Anthony och hans $nn$ vänner är på restaurang och ska beställa mat. Menyn har $mm$ rätter, och alla vännerna har från början valt rätter som de vill ha. Anthony blir dock gladare ju fler olika rätter sällskapet beställer, så att han får se mer av vad restaurangen har att erbjuda. Han kan till och med tänka sig att betala för vännernas mat för att höja antalet olika beställda rätter.

Idag vill Anthony att vännerna ska beställa minst $kk$ olika rätter. Han kan få en vän att byta beställning till en dyrare rätt genom att betala mellanskillnaden mellan kostnaden för vännens ursprungliga val och den dyrare rätten (men varje person beställer fortfarande bara en sak). Han kan göra så många sådana byten som han vill.

Givet antalet rätter, deras kostnader, och vännernas ursprungliga beställningar, vad är det minsta Anthony behöver betala för att kunna se till att vännerna beställer minst $kk$ olika rätter?

입력

Den första raden innehåller tre heltal $nn$, $mm$ och $kk$, antalet vänner, antalet rätter och det önskade antalet unika beställningar ($1\le n,m\le 2\cdot {10}^{5}1\; \backslash leq\; n,\; m\; \backslash leq\; 2\; \backslash cdot\; 10^5$, $1\le k\le n1\; \backslash le\; k\; \backslash le\; n$). \\ Därefter kommer en rad med $nn$ heltal $x_1\dots x_{n}x\_1\; \backslash dots\; x\_n$, där $x_{i}x\_i$ ($1\le x_i\le m1\; \backslash leq\; x\_i\; \backslash leq\; m$) är den rätt som vän $ii$ från början vill köpa. \\ Därefter kommer en rad med $mm$ heltal $c_1\dots c_{m}c\_1\; \backslash dots\; c\_m$, där $c_{i}c\_i$ ($1\le c_i\le {10}^{9}1\; \backslash leq\; c\_i\; \backslash leq\; 10^9$) är kostnaden för rätt $ii$.

출력

Ett heltal, det minsta beloppet som Anthony behöver betala för att vännerna ska beställa minst $kk$ olika rätter. Om det är omöjligt, skriv ut $-1-1$. Notera att svaret inte nödvändigtvis får plats i ett $3232$-bitars heltal.

힌트

I det första exempelfallet kan Anthony betala $22$ kronor för att vän $11$ ska byta från den första till den tredje rätten. Efter det beställs $33$ unika rätter: rätt $11$, rätt $22$ och rätt $33$.

I det andra exempelfallet finns det två rätter som båda kostar $1010$ kronor, och båda vännerna har valt den första rätten. Då det inte finns någon dyrare rätt än den första kan inte Anthony göra något för att ändra vännernas val, och kan aldrig uppnå $22$ unika rätter. Svaret blir då $-1-1$.

I det tredje exempelfallet vill vännerna redan ha två olika rätter, så Anthony behöver inte betala någonting.

I det sista exempelfallet vill Anthony se till att alla $88$ vänner beställer olika rätter. Det billigaste alternativet här är att betala för att vän $33$, $44$, $77$ och $88$ ska uppgradera till en av $10000000001\backslash ,000\backslash ,000\backslash ,000$-kronorsrätterna. Totalt kostar det $39999999903\backslash ,999\backslash ,999\backslash ,990$ kronor.

3 4 3
1 1 2
1 2 3 4

2

2 2 2
1 1
10 10

-1

2 2 1
1 2
10 10

0

8 8 8
1 2 3 4 1 2 3 4
1 2 3 4 1000000000 1000000000 1000000000 1000000000

3999999990