ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2016

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Technical debt

Time limit: 2.0 second
Memory limit: 256 MB
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, biX').
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.

Input

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).

Output

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.

Samples

inputoutput
5 3
0 1 5
5 1 0
6
3 2 1 
4 4
3 0 1 2
7 8 2 3
19
1 4 3 2 
Problem Author: Nikita Burlakov
To submit the solution for this problem go to the Problem set: 2084. Technical debt