Problem
Doanh nghiệp "Tự động-2010" sản xuất động cơ cho những chiếc xe hơi nổi tiếng thế giới. Động cơ gồm có đúng n bộ phận được đánh số từ 1 đến n, còn bộ phận đánh số i được thực hiện trong số pi giây. Các chi tiết cụ thể của doanh nghiệp "Auto-2010" là chỉ có một bộ phận động cơ có thể được sản xuất ở đó tại một thời điểm. Một số bộ phận yêu cầu sản xuất một bộ các bộ phận đúc sẵn khác.
Tổng giám đốc "Auto-2010" đặt ra một nhiệm vụ đầy tham vọng cho doanh nghiệp — sản xuất phần số 1 trong thời gian sớm nhất để trình làng tại triển lãm.
Cần phải viết một chương trình, với sự phụ thuộc của thứ tự sản xuất giữa các bộ phận, sẽ tìm ra thời gian ngắn nhất để có thể sản xuất bộ phận số 1.
Đầu vào
Dòng đầu tiên của tệp đầu vào chứa số n (1≤ n ≤ 100000) — số bộ phận động cơ. Dòng thứ hai chứa n số nguyên dương p
1, p
2, p
n, xác định thời gian sản xuất của từng bộ phận tính bằng giây. Thời gian chế tạo từng bộ phận không quá 10
9 giây.
Mỗi dòng trong số n dòng tiếp theo của tệp đầu vào mô tả các đặc điểm của quá trình sản xuất các bộ phận. Ở đây, dòng thứ i chứa số phần ki cần thiết để tạo ra phần số i, cũng như số của chúng. Không có số bộ phận trùng lặp trong dòng thứ i. Tổng của tất cả các số k
i không vượt quá 200000.
Được biết, không có sự phụ thuộc theo chu kỳ trong quá trình sản xuất các bộ phận.
Dấu ấn
Dòng đầu tiên của tệp đầu ra phải chứa hai số: thời gian tối thiểu (tính bằng giây) cần thiết để sản xuất bộ phận số 1 càng sớm càng tốt và số k bộ phận cần được sản xuất cho việc này. Trong dòng thứ hai, bạn cần in k số cách nhau bằng dấu cách — số bộ phận theo thứ tự mà chúng sẽ được sản xuất để sản xuất bộ phận số 1 càng sớm càng tốt.
| Đầu vào |
Đầu ra |
3
100 200 300
1 2
0
2 2 1
| 300 2
2 1
|
2
23
1 2
0 |
5 2
2 1
|
4
2 3 4 5
2 3 2
1 3
0
2 1 3
| 9 3
3 2 1
|