Centre for Gifted Education - Hanoi university of Technology

Có N chi tiết máy cần được gia công lần lượt trên 3 máy A , B và C.

Thời gian gia công chi tiết i trên máy A là a[i] , thời gian gia công trên máy B là b[i] , thời gian gia công trên máy C là c[i] .

Biết rằng 1 trong 2 điều kiện sau đây được thoả mãn :

+ max( b[i] ) ≤ min( a[i] ) hoặc

+ max( b[i] ) ≤ min( c[i] ) ( i = 1,…n )

Hãy tìm trình tự gia công các chi tiết trên 3 máy sao cho việc hoàn thành gia công tất cả các chi tiết là sớm nhất có thể .

Tham khảo thuật toán Johnson

Input

Dòng 1 : số nguyên dương N ( 1 ≤ N ≤ 1000 ) .
Dòng 2 : N số nguyên dương a[1] , … a[n] . ( 1 ≤ a[i] ≤ 10000 )
Dòng 3 : N số nguyên dương b[1] , … b[n] .( 1 ≤ b[i] ≤ 10000 )
Dòng 4 : N số nguyên dương c[1] , … c[n] .( 1 ≤ c[i] ≤ 10000 )

Output

Dòng 1 : Số nguyên dương T là thời điểm sớm nhất có thể hoàn thành .
Dòng 2 : N số nguyên là lịch trình gia công các chi tiết máy .

Example

Input:
2
1 2
3 2
4 4

Output:

12
1 2