1319 - 卡车上的最大单元数
Time Limit : 1 秒
Memory Limit : 128 MB
请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：
numberOfBoxesi是类型i的箱子的数量。numberOfUnitsPerBoxi是类型i每个箱子可以装载的单元数量。
整数 truckSize 表示卡车上可以装载 箱子 的 最大数量 。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。
输出卡车可以装载 单元 的 最大 总数。
Input
第一行为1个整数n，表示有n种箱子
以下n行每行2个数字，分别表示箱子的数量和每个箱子可以装载的单元
第 n+2 行为一个整数，表示能够卡车上能装载箱子的最大数量
Output
卡车可以装载 单元 的 最大 总数
Examples
Input
3 1 3 2 2 3 1 4
Output
8
Input
4 5 10 2 5 4 7 3 9 10
Output
91
Hint
1 <= boxTypes.length <= 1000
1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
1 <= truckSize <= 10^6