TWO Spoj – Lập lịch trên hai máy

Nguồn đề bài: http://vn.spoj.com/problems/TWO/

1. Đề bài TWO Spoj

Có N chi tiết máy cần được gia công lần lượt trên 2 máy A và B. 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]. Hãy tìm trình tự gia công các chi tiết trên 2 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)

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:

3

2 3 1

1 2 3

Output:

7

3 2 1

2. Gợi ý TWO Spoj

– Các bạn dùng thuật toán Jonhson ^^

3. Code Tham Khảo TWO Spoj

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *