It was not long ago when Pasha has entered his first job. Pasha is an experienced ACM player, so refinement of a large module of the system was put in his hands right away. Several generations of developers had worked on that module. Not all of them were skillful and experienced, which resulted in a substantial technical debt in the code: bugs, unjustified redundancy, intricate logic, and other annoying issues.
"This will not do! Gotta refactor everything ASAP!" — exclaimed Pasha once he opened his IDE. Having recovered from the shock, Pasha estimated the volume of technical debt at number X. Unfortunately, tough manager does not allow him to refactor the old code all day long, and requires him to implement various tasks requested by the clients. In total Pasha has to complete N Very Important client tasks.
Having read Fowler, Pasha understands that technical debt decreases the utility of new task implementation. Upon certain meditation, for each task i Pasha has estimated the volume of technical debt that can be discarded during its implementation — ai, and its utility bi. So now he will approach each of N tasks the following way:
- Firstly Pasha will rewrite a part of initial code, thus momentarily decreasing technical debt by ai. Of course, technical debt cannot be less than zero.
- Then Pasha will write the code that immediately resolves the assigned task. In an ideal world this code would yield bi of utility to the project, but in a system with technical debt of X' resolving the task will produce the utility of just max(0, bi − X').
Pasha is a good programmer, and his code does not increase technical debt (at least he thinks so).
The tough manager desires to maximize the utility yielded by resolving all tasks, and is anything but concerned with the volume of technical debt. Task resolution order does not make any difference to the manager as well.
Help Pasha place tasks in an order providing maximum overall utility.
The first line contains two integer numbers X and N separated by space (0 ≤ X ≤ 100, 1 ≤ N ≤ 200). The second line contains N integer numbers a1, a2, …, an (0 ≤ ai ≤ 100). The third line contains N integer numbers b1, b2, …, bn (0 ≤ bi ≤ 106).
In the first line output maximum total utility that can be obtained upon solving N tasks. In the second line output a permutation of N numbers — numbers of tasks in the order Pasha should resolve them. If several answers exist, output any.
0 1 5
5 1 0
3 2 1
3 0 1 2
7 8 2 3
1 4 3 2
Problem Author: Nikita Burlakov