CF717C Potions Homework

Harry Water、Ronaldo、Her-my-oh-knee 以及他们的朋友们在 MDCS Speechcraft and Misery 学校开始了新的学年。此时，他们非常高兴能与分别已久的朋友们重逢。阳光明媚，鸟儿歌唱，花儿盛开，而他们的魔药课老师 Snipe 教授则依旧郁郁寡欢。由于对自己人生的失落感和不满，他给大家布置了很多魔药课程的作业。 每个学生分配到了一项任务。有些学生完成某些任务的速度比其他人快。因此，他们希望重新分配任务，使得每个人依然执行一项任务，且所有任务都能够完成。每位学生都有自己的懒惰程度，每项任务也有自身的难度。Snipe 教授极力培养学生的职业操守，因此每个学生的懒惰程度等于他所接任务的难度。这两组值都由序列 $a$ 给出，其中 $a_i$ 既代表第 $i$ 个学生的懒惰程度，也代表他所接任务的难度。 一个学生完成某项任务所花的时间等于他的懒惰程度和任务难度的乘积。他们想知道，如果以最优方式分配这些任务，完成所有任务所需的总时间最小是多少。每个人应分配一项任务，每项任务也只能分配给一人。请输出最小的总时间对 $10007$ 取模的结果。

输入的第一行包含整数 $n$（$1 \leq n \leq 100000$），表示任务的数量。接下来的 $n$ 行中，每行包含一个整数 $a_i$（$1 \leq a_i \leq 100000$），表示初始任务的难度和第 $i$ 位学生的懒惰程度。

输出完成所有任务所需最小总时间对 $10007$ 取模的结果。

在第一个样例中，如果学生互换任务，则能够在 $3+3=6$ 个时间单位内完成全部任务。 由 ChatGPT 5 翻译