시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB444100.000%

문제

Nicole och Simon spelar ett kortspel som består av $N$ rundor. I runda $i$ lägger Nicole ut ett kort som har ett tal $a_i$ skrivet på sig. Simon måste då svara med att lägga ut ett kort från sin hand. Om Simons kort har värde $b_i$ så får Nicole $|a_i-b_i|$ poäng. Simon vill alltså lägga ett kort som är så nära det Nicole lade som möjligt.

Givet exakt vilka kort Nicole kommer lägga ut och vilka $M$ kort Simon har på sin hand från början, vad är den minsta poängen Nicole kan få om Simon spelar optimalt? $M$ är alltid lika med $N$ eller $N+1$.

입력

Den första raden innehåller de två heltalen $N$ ($1\leq N \leq 2 \cdot 10^5$) och $M$ ($N\leq M \leq N+1$).

Den andra raden innehåller $N$ heltal, där det $i$:te talet $a_i$ ($0\le a_i \le 10^9$) är värdet på kortet Nicole lägger ut i runda $i$.

Den tredje raden innehåller $M$ heltal, där det $i$:te talet $b_i$ ($0\le b_i \le 10^9$) är värdet av det $i:$te kortet Simon har på sin hand.

출력

Skriv ut ett heltal -- den minsta totala poängen Nicole får om Simon spelar optimalt.

예제 입력 1

2 3
1 10
2 0 1

예제 출력 1

8

예제 입력 2

3 3
4 8 1
5 1 2

예제 출력 2

5

예제 입력 3

4 5
6 10 6 2
1 4 0 6 3

예제 출력 3

10

예제 입력 4

5 5
0 0 0 0 0
1000000000 1000000000 1000000000 1000000000 1000000000

예제 출력 4

5000000000

힌트

I exempelfall 1 är det optimalt för Simon att i första rundan lägga ut kortet med värde 1, och i andra rundan lägga ut kortet med värde 2. Då får Nicole $|1-1| + |10-2|=8$ poäng.

I exempelfall 2 spelar Simon ut korten av värde 2, 5, 1, i den ordningen.

I exempelfall 3 spelar Simon ut korten av värde 4, 6, 3, 1, i den ordningen.

출처

Olympiad > Swedish Olympiad in Informatics > 2022 > Final B번

  • 문제를 만든 사람: Abdullah Zaghmout