MACHINE - Lập lịch trên 3 máy

Giới hạn
  • Thời gian: 0.134s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 20000 bytes

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

Input

Dòng 1 : số nguyên dương N ( 1 ≤ N ≤ 10000 ) .
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


  • Người up: hard7771988
  • Nguồn bài: Folklore