Choix des skis – Qualification 2017

É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$