仓库搬迁

题目描述

城市中共有 $n$ 个仓库。第 $i$ 个仓库当前存放了 $a_i$ 件物品，最多能存放 $c_i$ 件物品，其中 $0\le a_i\le c_i$。

为了降低管理成本，你需要关闭一部分仓库。关闭某个仓库时，其中的全部物品都必须搬入仍然保留的仓库；保留仓库中原有的物品不需要搬动。物品可以任意分配到保留仓库的空余位置，但任何仓库最终存放的物品数都不能超过它的容量。

管理部门按以下先后顺序评价方案：

1. 保留的仓库数量尽量少；
2. 在保留仓库数量最少的前提下，搬迁的物品总数尽量少。

请输出最少需要保留多少个仓库，以及在此前提下最少需要搬迁多少件物品。

输入格式

第一行输入一个整数 $n$，表示仓库数量。

接下来 $n$ 行，每行输入两个整数 $a_i,c_i$，分别表示第 $i$ 个仓库当前的物品数和容量。

输出格式

输出两个整数，分别表示最少保留的仓库数量，以及在此前提下最少搬迁的物品数。

样例 1

输入

4
4 8
3 6
2 5
1 4

输出

2 3

说明

所有仓库中共有 $10$ 件物品。保留容量为 $8$ 和 $6$ 的两个仓库已经足够，并且不可能只保留一个仓库。在所有保留两个仓库的方案中，最多可以让 $7$ 件原有物品留在原仓库，因此最少搬迁 $10-7=3$ 件。

样例 2

输入

1
5 9

输出

1 0

更多样例

样例 3、样例 4 和样例 5 请分别查看选手目录中的 Data/sample3.in、Data/sample3.ans，Data/sample4.in、Data/sample4.ans，以及 Data/sample5.in、Data/sample5.ans。

【数据规模与约定】

保证 $1\le n\le 60$，$0\le a_i\le c_i\le 3000$，且 $1\le\sum a_i\le3000$。

点击下载本题选手目录