D. PRJCHAIN - Chuỗi dự án

Công ty X nhận làm dự án đánh số từ tới để cải tạo các công trình công cộng và các địa điểm tham quan du lịch của thành phố. Dự án thứ cần công ty X đầu tư một khoản tiền là để mua vật liệu và sau khi hoàn thành dự án thứ , công ty X sẽ được thành phố trả cho khoản tiền công là . Sau khi đã hoàn thành cả dự án, thành phố sẽ chi trả hết những khoản tiền mà công ty đã đầu tư để mua vật liệu và công ty sẽ thu được lợi nhuận đáng kể từ số tiền công đã được nhận qua từng dự án. Vấn đề duy nhất đặt ra là công ty phải huy động một số vốn ban đầu để chi trả những khoản đầu tư khi mà thành phố chưa nghiệm thu toàn bộ các dự án.

Biết rằng công ty X có thể thực hiện các dự án theo thứ tự tùy ý, hãy cho biết số vốn ban đầu ít nhất cần huy động và thứ tự thực hiện các dự án với số vốn đó.

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương ;
• Dòng thứ hai chứa số nguyên dương ;
• Dòng thứ ba chứa số nguyên dương .

Dữ liệu ra:

• Dòng đầu ghi một số nguyên là số vốn ban đầu ít nhất cần huy động;
• Dòng thứ hai ghi số nguyên theo thứ tự là số hiệu các dự án từ dự án được thực hiện đầu tiên tới dự án được thực hiện cuối cùng.

Các số trên một dòng được ghi cách nhau ít nhất một dấu cách.

Ví dụ

Dữ liệu vào:

6
6 3 1 2 4 9
2 4 3 1 3 2

Dữ liệu ra:

11
3 2 5 1 6 4

Giải thích:

• Vốn ban đầu là ;
• Làm dự án chi (vốn ), thu (vốn ;
• Làm dự án chi (vốn ), thu (vốn );
• Làm dự án chi (vốn ), thu (vốn );
• Làm dự án chi (vốn ), thu (vốn );
• Làm dự án chi (vốn ), thu (vốn );
• Làm dự án chi (vốn ), thu (vốn ).