Buffcraft#7493
Brenda enjoys a new role-playing game Buffcraft. Shields, swords, books and other carry-on items do not affect character stats in Buffcraft. The only way to increase the stats of your character is to buff her.
There are two types of buffs in Buffcraft. Direct buffs increase a base value of the stat, while percentage buffs increase stats by the fraction of the base value. To be precise, if unbuffed base value of your character stat is , you have buffed her using direct buffs of strength d_1, d_2, ..., d_n and percentage buffs of strength p_1, p_2, ..., p_m, the resulting stat will be equal to ( + d_1 + d_2 + ... + d_n)( + p_1 + p_2 + ... + p_m) / . Note that the resulting stat may be fractional.
Unfortunately, your character has only buff slots and if you apply more than buffs on her, only thelast buffs remain active. Thus, there is no reason to apply more than buffs simultaneously. You cannot apply the same buff more than once.
Brenda is going to send her character to raid and wants to buff her health to maximal possible value. She has some direct and some percentage buffs at her disposal and needs your help to select the set of buffs that leads to maximal possible total health.
The first line contains four integers , , c_d and c_p - the base health of the character, the number of buff slots, the number of available directs buffs, and the number of available percentage buffs.
The following line contains c_d integers d_i - strengths of direct buffs.
The last line contains c_p integer numbers p_i - strengths of percentage buffs.
All numbers are greater than or equal to zero, and less than or equal to fifty thousand.
The first line must contain two integers and - the number of direct and percentage buffs to use ( ≤ ≤ c_d, ≤ ≤ c_p, ≤ + ≤ ).
The following line must contain different numbers - indices of direct buffs to apply (buffs are numberedfrom one).
The last line must contain different numbers - indices of percentage buffs to apply (also numbered from one).
The resulting total health after application of all + buffs must be maximal possible.
Beispiel 1
Beispiel 2