Choix des skis – Qualification 2017

Level 3

Énoncé

Cette année, tout le monde veut faire du ski, mais Joseph Marchand travaille seul et il est débordé ! Il a encore besoin de votre aide. Cette fois vous n’aurez pas à vous occuper d’un client, mais de plusieurs à la fois ! Comme Joseph est prévoyant, il vous a donné un stock de paires de skis aussi grand que le nombre de clients (noté $N$). Comme Joseph n’a toujours pas toutes les tailles, il vous demande de faire au mieux correspondre ces tailles de skis (notés $S_i$) aux tailles des clients (notés $P_i$).

Vous cherchez à distribuer les skis de manière à limiter le plus possible la déception des clients. La déception d'une attribution est la somme, pour chaque client, de la différence entre sa taille et celle de la paire de skis qu’il a reçue. Ainsi Joseph peut être sûr de répondre au mieux aux attentes de tous ses clients.

Entrée

L'entrée contiendra trois lignes. La première donnera le nombre de clients $N$, la deuxième la liste des tailles des personnes, $P_i$, et la troisième listera les tailles des paires de skis $S_i$.

Sortie

Vous afficherez un entier, la déception minimale.

Contraintes

  • $0 \le N \le 100\ 000$
  • $0 \le P_i \le 1\ 000\ 000\ 000$
  • $0 \le S_i \le 1\ 000\ 000\ 000$

Runtime constraints

Maximum memory usage
5000 kilobytes
Maximum execution time
500 milliseconds

Input/output samples

Sample input
2
2 5
4 1
Sample output
2
Sample input
5
2 4 8 16 32
12 1 60 4 25
Sample output
42

Submit your solution

You have to register or log in to be able to submit your solution.