# Sort two list of jobs result in minimum execution time

Two twins, James Johnson and Jonathan Johnson, work at a factory which produces bicycles. Their job is probably the most important one: James attaches the front wheel, and Jonathan does the same with the rear wheel. At the beginning of their working day, they receive construction kits, consisting of the front wheel, the rear wheel, and the rest of the bicycle. It is known that:

• for the i-th construction kit, James will attach the front wheel in Ai seconds;
• for the i-th construction kit, Jonathan will attach the rear wheel Bi in seconds;
• James and Jonathan cannot work on the same bicycle simultaneously;
• the front wheel must be attached earlier than the rear wheel.

James and Jonathan are very experienced in assembling bicycles. In fact, given the information about all construction kits, they act optimally, such that the last wheel is attached as early as possible. However, the new director of the factory is not yet that experienced, so she needs some help. Please write her a program which tells how fast the twins assemble all today's bicycles, and how exactly this could be done.

Input

The first line of the input file contains N, the number of bicycle construction kits.

The second line contains N integers, the i-th of them equals Ai. The third line also contains N integers, the i-th of them equals Bi. All Ai and Bi are positive and do not exceed 10^9.

Output

In the first line, output the minimum time needed to assemble all bicycles.

The second line must contain integers. Of them, the i-th integer denotes the moment of time James starts to assemble the i-th construction kit. The third line must contain integers, this time for Jonathan. If several optimal scenarios exist, output any of them.

Examples

input.txt 3

1 2 3

2 1 3

output.txt 8

0 4 1

1 7 4

My solution is a greedy approach, sorting the sequences of pair (Ai, Bi) and (Ai+1, Bi+1). If execute the sequence in order i+1 -> i takes less time that i -> i+1, then swap them. So far it passes 13 test cases and fails on a test case with quite close result. The expected output is 29 while my solution yields 31. If anybody can help please give me a hint, thank you in advance.

I use Java, I implement a class called Job which stores a pair of Ai, Bi and the original index.

static class Job implements Comparable<Job> {
long a;
long b;
int index;

public Job(long a, long b, int index) {
this.a = a;
this.b = b;
this.index = index;
}

@Override
public int compareTo(Job that) {
long thisTime = this.a + Math.max(this.b, that.a) + that.b;
long thatTime = that.a + Math.max(this.a, that.b) + this.b;

return Long.compare(thisTime, thatTime);
}

@Override
public String toString() {
return "(" + a + "," + b + ") - " + index;
}
}

public static void solve(long[] a, long[] b, int[] order) throws IOException {
long[][] start = new long[2][a.length];
int prev = -1;
for (int i : order) {
if (prev == -1) {
start[0][i] = 0;
start[1][i] = a[i];
} else {
start[0][i] = start[0][prev] + a[prev];
start[1][i] = Math.max(start[1][prev] + b[prev], start[0][i] + a[i]);
}

prev = i;
}

long time = start[1][prev] + b[prev];
bw.write(time + "\n");
for (int i = 0; i < start.length; ++i) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < start[0].length; ++j)
sb.append(start[i][j] + " ");
bw.write(sb.toString().trim() + "\n");
}
}

• Please show the input that should produce the answer $29.$ Also, you had better show us your algorithm in more detail. – saulspatz Apr 26 at 12:17
• It seems ambiguous whether all the parts for a bicycle must come from the same indexed construction kit or not. – DanielV Apr 26 at 12:21
• @saulspatz it's just the hint from the judge, they don't show the actual input. – Loc Truong Apr 26 at 12:24
• Sounds like an application test for a dev-job... – denklo Apr 26 at 12:28
• @denklo no, I'm following an algorithm course of ITMO on edx.org – Loc Truong Apr 26 at 12:28