Buffcraft: Maximizing Character Health

Brenda is playing Buffcraft, a role-playing game where the only way to improve your character's stats is by applying buffs. There are two types of buffs:

• Direct Buffs: These add a constant value d to the base stat.
• Percentage Buffs: These increase the stat by a percentage of the base value.

If the unbuffed stat is \(b\), and you apply some direct buffs with strengths \(d_1,d_2,\dots,d_n\) and percentage buffs with strengths \(p_1,p_2,\dots,p_m\), then the final stat is computed as:

[ \text{Final Stat} = \frac{\left(b + \sum_{i=1}^{n} d_i\right) \times \left(100 + \sum_{j=1}^{m} p_j\right)}{100} ]

Your character has only \(k\) buff slots. If more than \(k\) buffs are applied, only the last \(k\) remain active. Therefore, you should choose at most \(k\) buffs from the available ones (each available at most once) to maximize your character's health. It is guaranteed that all buff strengths are non-negative.

You are given the unbuffed base health \(b\), the maximum number of buffs \(k\), followed by the number of direct buffs (\(n\)) and percentage buffs (\(m\)). Then you are given \(n\) direct buff values and \(m\) percentage buff values. Determine the maximum possible total health after applying at most \(k\) buffs optimally.

inputFormat

The input consists of four lines:

1. The first line contains two integers \(b\) and \(k\) (\(1 \leq b \leq 10^9\), \(1 \leq k \leq 10^5\)), representing the base health and the number of buff slots.
2. The second line contains two integers \(n\) and \(m\) (\(0 \leq n, m \leq 10^5\)), representing the number of available direct buffs and percentage buffs respectively.
3. The third line contains \(n\) non-negative integers, each representing a direct buff strength.
4. The fourth line contains \(m\) non-negative integers, each representing a percentage buff strength.

Note: It is allowed to choose fewer than \(k\) buffs if that leads to an optimal result.

outputFormat

Output a single number representing the maximum possible total health after applying at most \(k\) buffs. The answer can be fractional.

sample

100 2
3 2
30 20 10
50 30

195.0