题目描述

Brenda enjoys a new role-playing game Buffcraft. Shields, swords, books and other carry-on items do not affects 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 $b$ , you have buffed her using $n$ direct buffs of strength $d_1 , d_2 , \cdots d_n$ and $m$ percentage buffs of strength $p_{1}, p_{2}, \cdots , p_{m},$ the resulting stat will be equal to $(b + d_{1} + d_{2} + · · · + d_{n})(100 + p_{1} + p_{2} + · · · + p_{m})/100$ . Note that the resulting stat may be fractional.

Unfortunately, your character has only $k$ buff slots and if you apply more than $k$ buffs on her, only the last $k$ buffs remains active. Thus, there is no reason to apply more than $k$ buffs simultaneously. You cannot apply the same buff more than once.

Brenda is going to send his 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 of the input file contains four integers $b , k , 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 of the input file contains $c_{p}$ integer numbers $p_{i}$ — strengths of percentage buffs.

All numbers in the input file are greater than or equal to zero, and less than or equal to fifty thousand.

输出格式

The first line of the output file must contain two integers $n$ and $m$ — the number of direct and percentage buffs to use $(0 \le n \le c_{d}; 0 \le m \le c_{p}; 0 \le n + m \le k)$ .

The following line must contain $n$ different numbers — indices of direct buffs to apply (buffs are numbered from one).

The last line of the output must contain $m$ different numbers — indices of percentage buffs to apply (also numbered from one).

The resulting total health after application of all $n + m$ buffs must be maximal possible.

题目大意

题目描述

Brenda喜欢一款新的游戏Buffcraft。没有任何物品可以影响Buffcraft中的角色属性。增加你角色属性的唯一方法就是给予它buff。

Buffcraft中有两种类型的buff。
1.直接增加buff的值;
2.百分比增加buff的值;
如果你的角色buff初始值是$b$，那么你使用$n$个增益分别为$d_1,d_2,\cdots,d_n$的第一种buff和$m$个增益分别为$p_{1},p_{2}\cdots,p_{m}$的第二种buff，得到的结果将等于$(b+d_{1}+d_{2}+··+d_{n})(100+p_{1}+p_{2}-··+p_{m})/100$。请注意，这个结果可能不是整数。

不幸的是，你的角色只有$k$个buff槽，如果你在她身上应用了$k$个以上的buff，那么只有最后的$k$个buff有效。因此，你不能同时拥有$k$个以上buff。当然，一个buff不能被多次使用。

Brenda将派她的角色去战斗，并希望将角色的buff值提升到最大。有一些第一种buff和一些第二种buff可供她使用。她需要你的帮助来选择一种buff的搭配方式，以获得最大可能的总buff值。

输入格式

第一行包含四个整数$b,k,n,m$；分别代表角色的基础buff值、buff槽数、第一种buff的数量与第二种buff的数量。
第二行包含$n$个整数$d_{i}$，代表每个第一种buff的增益量。
第三行包含$m$个整数$p_{i}$，代表每个第二种buff的增益量。

输出格式

第一行是两个整数$x,y$代表用了多少第一种buff和用了多少第二种buff。$(0 \le x \le n; 0 \le y \le m; 0 \le x + y \le k)$ .

第二行是$x$个数字-要应用的每一个第一种buff的索引。
第二行是$y$个数字-要应用的每一个第二种buff的索引。 你的方案要让所有buff应用后产生的总buff值尽可能最大。

输入输出样例

样例输入#1

70 3 2 2
40 30
50 40

样例输出#1

2 1
2 1
1

样例输入#2

1 2 3 4
6 6 5
8 10 7 9

样例输出#2

2 0
1 2

说明/提示

$0 \le b,k,n,m,d_{i},p_{i} \le 50000$
数组的索引从1开始
时间限制:2s;空间限制:256MB。

70 3 2 2
40 30
50 40

2 1
2 1
1

1 2 3 4
6 6 5
8 10 7 9

2 0
1 2

提示

Time limit: 2 s, Memory limit: 256 MB.