程基会长认为新生都该给他送礼，新生小成想要获得一个好印象，他打算送出一份大礼。
而狡诈的程基会长因为怕收礼太多被发现，所以拍脑袋决定一个人最多收 个礼物。
现在小成的奢侈品收藏室里面有 种不同品牌的礼物，每种品牌的礼物有 的数量与 的单价。
其中如果赠送同一品牌的礼物超过 个，后续小成再次选择该品牌的礼物时，会认为它的价值只有原先的 ，
这是因为同种礼物选的数量赠送太多了（程基会长不高兴了！）
请你求出小成如何送出最大价值的礼物来讨好程基会长的欢心！
第一行三个用空格分隔的正整数 ，表示小成有 种品牌的礼物，选择同一种超过 个后贬值，小成所需要选择的礼物总个数 。
随后 行，用空格分隔的正整数 ，表示第 种礼物的数量和单价。题目保证礼物总数大于 。
输出一行一个实数 ，保留一位小数点，表示小成选择 个礼物后的最大价值。
输入样例
3 2 5 6 1 3 2 1 8
输出样例
14.0