任务匹配
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
有 名同学和 个训练任务。
第 名同学的能力值为 ,第 个训练任务的难度为 。
一名同学最多只能完成一个任务,一个任务也最多只能由一名同学完成。
如果某名同学的能力值不小于某个任务的难度,那么这名同学就可以完成这个任务。也就是说,当:$$a_i \ge b_j$$时,同学 可以完成任务 。
现在请你安排同学完成任务,使完成的任务数量尽可能多。
如果有多种安排方案都能完成最多任务,请在这些方案中,使被安排同学的能力值总和尽可能小。
请输出:
- 最多可以完成多少个任务;
- 在完成任务数量最多的前提下,被安排同学能力值总和的最小值。
输入格式
第一行包含两个整数 ,分别表示同学数量和任务数量。
第二行包含 个整数:,表示每名同学的能力值。
第三行包含 个整数:,表示每个任务的难度。
输出格式
输出一行两个整数,分别表示最多完成的任务数量,以及在最多完成任务数量前提下,被安排同学能力值总和的最小值。
5 4
3 8 5 10 6
4 6 7 2
4 22
样例解释
一种最优安排为:
- 能力值为 的同学完成难度为 的任务;
- 能力值为 的同学完成难度为 的任务。
- 能力值为 的同学完成难度为 的任务;
- 能力值为 的同学完成难度为 的任务;
最多可以完成 个任务,被安排同学能力值总和为:$$3+5+6+8=22$$可以证明这是最优的情况。
4 3
1 1 1 1
5 6 7
0 0
样例解释
很明显,一个都完成不了。
数据范围与约定
对于所有测试数据,保证:$1 \le n,m \le 2\times 10^5,\quad 1 \le a_i,b_i \le 10^9$