Buffcraft

Interview

Time limit2sMemory limit256 MB

Summary

Pick at most k direct and percentage buffs so the boosted base times the percentage multiplier is as large as possible.

Level: Easy3 of 10
Topics: Sorting, Greedy, Brute force
Solved: No attempts yet

Problem

Brenda plays the role playing game Buffcraft. Shields, swords, books and other carried items do not change a character's stats in Buffcraft. The only way to raise a stat is to buff the character.

Buffcraft has two kinds of buffs. A direct buff raises the base value of a stat, and a percentage buff raises the stat by a fraction of that base value. To be precise, if the unbuffed base value of a stat is $b$ and the character carries $n$ direct buffs of strength $d_1, d_2, \dots, d_n$ together with $m$ percentage buffs of strength $p_1, p_2, \dots, p_m$ , the resulting stat equals $(b + d_1 + d_2 + \dots + d_n)(100 + p_1 + p_2 + \dots + p_m)/100$ . The resulting stat can be fractional.

A character has only $k$ buff slots. If more than $k$ buffs are applied, only the last $k$ stay active, so there is no reason to apply more than $k$ buffs at once. The same buff cannot be applied twice.

Brenda is about to send her character on a raid and wants its health as high as possible. Choose the set of buffs that gives the maximum total health.

Input

The first line contains four integers $b$ , $k$ , $c_d$ , $c_p$ : the base health of the character, the number of buff slots, the number of available direct buffs, and the number of available percentage buffs.

The second line contains $c_d$ integers $d_i$ , the strengths of the direct buffs.

The third line contains $c_p$ integers $p_i$ , the strengths of the percentage buffs.

Every number in the input is at least 0 and at most 50000. If $c_d$ or $c_p$ is 0, the matching line is empty.

Output

Print on the first line the number $n$ of direct buffs and the number $m$ of percentage buffs to apply ( $0 \le n \le c_d$ , $0 \le m \le c_p$ , $0 \le n + m \le k$ ).

Print on the second line the $n$ indices of the chosen direct buffs in increasing order. Buffs are numbered from 1.

Print on the third line the $m$ indices of the chosen percentage buffs in increasing order.

If $n$ or $m$ is 0, print an empty line in its place.

Several sets of buffs can reach the maximum health, so print the set that the following rule selects.

Sort the direct buffs by decreasing strength, putting the smaller index first when two strengths are equal. Sort the percentage buffs the same way.
For each $n$ from $0$ to $\min(k, c_d)$ , set $m = \min(k - n, c_p)$ and take the first $n$ direct buffs and the first $m$ percentage buffs of those sorted orders.
Among these candidates print the one with the largest resulting health. If several candidates give the same health, print the one with the smallest $n$ .

Examples6

Example 1
Input
```
70 3 2 2
40 30
50 40
```
Expected output
```
2 1
1 2
1
```
Example 2
Input
```
1 2 3 4
6 6 5
8 10 7 9
```
Expected output
```
2 0
1 2
```
Example 3
Input
```
100 0 3 3
1 2 3
10 20 30
```
Expected output
```
0 0
```
Example 4
Input
```
0 1 1 1
0
0
```
Expected output
```
0 1

1
```
Example 5
Input
```
5 3 0 2

7 9
```
Expected output
```
0 2

1 2
```
Example 6
Input
```
5 2 3 0
1 2 3
```
Expected output
```
2 0
2 3
```