题目内容

小张拥有多箱货物，每箱具有不同的重量和价值。现有一收购商提出，将以最低一箱货物的价值作为整体收购价格，且允许小张最多出售 $m$ 箱货物。请协助小张计算，在此条件下，他能够获得的最大总价值是多少。数值可能较大，最终结果与 $1000000007$ 取余后输出.

总价值的计算方法: $m$ 箱货物的总重量乘上 $m$ 箱货物中价值最小值

输入描述

输入为 $4$ 行

第一行为一个整数 $n$ ，代表货物的箱子总数， $0<=n<=10^5$

第二行为一个整数序列，长度为 $n$ ，分别代表货物每箱的重量，重量范围: $0<= weight<= 10^5$

第三行为一个整数序列，长度为 $n$ ，分别代表货物每箱的价格,价格范围: $0<= value<= 10^7$

第四行为一个整数 $m$ ，代表最多卖出的货物箱数 $0<=m<=n$

输出小张能获得最大价值，与 $1000000007$ 取余后输出

输入

6
2,11,3,6,5,8
5,9,3,9,7,5
3

输出

说明

分别选择重量和价格为 $[11,9],[6,9],[5,7]$ 三个箱子价值最大，总重量为 $11+6+5=22$ ，总价值 $22*7=154$

输入

3
5,7,3
2,9,3
2

输出

说明

分别选择重量和价格为 $[7,9]$ 的箱子价值最大，价值 $7*9=63$