Rating
题号:NC219917
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小 L 有 n 个 CF 号,每场比赛他会使用一个账号,会得到一个 Performance,假设原 Rating 为 x,Performance 为 y,则 Rating 变为

小 L 会贪心地选择自己每一次使用的号,使得 每场之后 CF Rating 之和最大,请您在每一场比赛之后输出他的 Rating 之和,保留两位小数。

换句话说,每场之前,小 L 根据当前自己所有号 Rating,选出一个号参加比赛,以最大化这场之后他的 Rating 之和。下一场时,之前的选择都会被保留,即使换一种选择可能使下一场后 Rating 和更大,也不能更换之前的选择。

输入描述:

第一行两个正整数 n,m,表示号的个数和比赛场数。

接下来一行 n 个整数,表示他每个号的 Rating。

之后 m 行,每行 1 个整数,表示小 L 的 Performance。

输出描述:

对于每一个询问,输出一个实数表示答案,保留两位小数。
示例1

输入

复制
5 5
2000 2100 2200 2300 2350
1900
1500
2200
2700
2000

输出

复制
10900.00
10675.00
10912.50
11281.25
11231.25

说明

对于 30\% 的数据, n,m\leq 3

对于 60\% 的数据, n,m\leq 10^3

对于另外 20\% 的数据, m=1\

对于 100\% 的数据, 1\leq n,m\leq 10^5, Rating 和 Performance 均为 1\sim 10^5 之间的整数。