雇佣工人

Time Limit: 1000MS

Memory Limit: 65535KB

Description

20年后,fishhead退休回家做了一个土财主,他想盖一栋超级大的房子来显示他的富有。

盖房子是个大工程,fishhead预计这个工程需要T个单位的工作量。现在有n个工人可以共选择。现在已知每个工人每小时能完成a[i]个单位的工作,他们每完成一个单位的工作酬劳是p[i]。现在fishhead想雇佣恰好k个工人帮忙盖房子。为了不让雇佣的工人闲着,现已知每个工人都是从开始一直工作到房子盖完成,即他们的工作时间是一样的。

问题是fishhead还要租用1个搅拌机来搅拌水泥,租金是每秒k元。

鱼头想知道最少花多少钱才能盖起这栋房子。

Input

第一行是Case数

对于每个case

每组case之间有空行

第一行是3个整数,n,k,T。0<k<=n<=60  0<=T<=100000

下面n行每行2个整数

a[i],p[i]  0<a[i],p[i]<=100000

Output

返回最小花费,精确到0.01

Sample Input

2

2 1 100
50 1000
60 2000

10 4 1000
1 20
2 30
3 40
4 58
5 60
6 70
7 80
8 90
9 100
10 150

Sample Output

107200.00
531764.71

Hint

所有的时间都可以是小数,对于的价格也按比例付。比如租用0.5秒的搅拌机,租金是0.5k元。

Source

沈宇亮

提交代码