Dũng từng là cựu học sinh chuyên Tin của Lê Hồng Phong. Thuở nhỏ, Dũng thường đạp xe từ Giao Thủy lên thành phố Nam Định để học. Dũng chia sẻ: “Em rất thích đạp xe, khi ngồi trên nó, em có cảm giác nhìn được cả thế giới”. Sau này, Dũng trở thành giám đốc công ty sản xuất động cơ cho những chiếc xe ô tô nổi tiếng thế giới. Công ty Dũng mang tên “DUNGSUPERCAR”. Động cơ bao gồm chính xác n phần, được đánh số từ 1 đến n, với phần i được sản xuất trong pi giây. Tính đặc thù trong động cơ Dũng sản xuất, là chỉ có một bộ phận động cơ được sản xuất tại một thời điểm. Tuy nhiên, để sản xuất một vài bộ phận, cần phải có một số các bộ phận khác được làm trước đó.

Với tư duy của chuyên Tin, Dũng đã đặt ra một nhiệm vụ đầy tham vọng cho công ty - trong thời gian ngắn nhất phải sản xuất được phần thứ 1 của động cơ, để giới thiệu nó tại triển lãm các động cơ nổi tiếng thế giới.

Cần phải viết một chương trình, đầu vào liên quan đến thứ tự sản xuất giữa các bộ phận của động cơ, tìm thời gian ngắn nhất trong đó phần 1 có thể được sản xuất.

Định dạng đầ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 làm nên động cơ của Dũng. Dòng thứ hai chứa n số nguyên dương p1, p2 ... pn, xác định thời gian sản xuất của từng bộ phận tương ứng. Thời gian để sản xuất mỗi bộ phận không vượt quá 10⁹ giây.

Mỗi dòng trong n dòng tiếp theo của tệp đầu vào mô tả các đặc tính của việc sản xuất các bộ phận. Ở đây, dòng thứ i chứa ki phần động cơ được yêu cầu để sản xuất phần thứ i, tiếp theo là chỉ số của các phần động cơ đó. Tổng của tất cả các số ki không vượt quá 200.000.

Được biết, không có sự phụ thuộc theo chu trình (vòng lặp) trong việc sản xuất các bộ phận.

Định dạng đầu ra

Dòng đầu tiên của tệp đầu ra 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 nhanh nhất phần 1 và số k, số lượng các bộ phận cần sản xuất. Trong dòng thứ hai, đầu ra k số được phân tách bằng khoảng trắng – chỉ số của phần động cơ theo thứ tự được sản xuất để sản xuất nhanh chóng phần 1.

Ví dụ về đầu vào và đầu ra