Gia công sản phẩm

Có n sản phẩm cần phải trãi qua thêm 2 giai đoạn gia công nữa mới hoàn thành (tạm gọi là giai đoạn a và giai đoạn b, mỗi sản phẩm phải trãi qua sự gia công của giai đoạn a mới có thể chuyển sang gia công giai đoạn b được). Khách hàng đang hối phải giao hàng gấp. Cửa tiệm có 2 máy gia công (1 máy gia công giai đoạn a và một máy gia công giai đoạn b). Mỗi sản phẩn điều có thời gian tiếu tốn cho từng giai đoạn gia công riêng biệt. Vấn đề đặt ra là gia công sản phẩm nào trước để đạt được thời gia ngắn nhất.

Input: file text giacong.inp cấu trúc như sau
* Dòng đâu tiên ghi số n (số lượng sản phẩm)
* n dòng tiếp theo mỗi dòng ghi 2 số với ý nghĩa là thời gian tiêu tốn của giai đoạn a và giai đoạn b

Output: file text giacong.out cấu trúc như sau
* Dòng đầu tiên chứa số k là tổng thời gian hoàn thành n sản phẩm
* Dòng tiếp theo chứa n số là thứ tự các sản phẩm cần phải được gia công.

Ví dụ
giacong.inp
2
4 1
3 5

giải thích: có 2 sản phẩm cần được gia công
- Sản phẩm thứ nhất tiêu tốn ở giai đoạn 1 là 4 đơn vị thời gian và tiêu tốn ở giai đoạn 2 là 1 đơn vị thời gian
- ...

giacong.out
9
2 1

giải thích: thời gia tiêu tốn để hoàn thành 2 sản phẩm là 9. Gia công sản phẩm 2 trước và sản phẩm 1 sau.

Giới hạn dữ liệu
1<=n<=1000
thời gian tiêu tốn trong từng giai đoạn của từng sản phẩm là các số nguyên có giá trị không quá 2000


alo0781.com