Phát huy tinh thần lá lành đùm lá rách của dân tộc, trong mùa dịch COVID19, tại địa điểm X, người dân được phát gạo miễn phí qua cây ATM gạo tự động. Cách thức hoạt động rất đơn giản, người đến lấy gạo sẽ xếp hàng trước cây chờ được phục vụ, người đến trước được phục vụ trước. Đến lượt mình, người đó sẽ bước lên nhận diện khuôn mặt qua máy tự động áp dụng công nghệ trí tuệ nhân tạo nhằm phát hiện các trường hợp gian lận lấy gạo nhiều lần. Sau khi xác thực, ATM gạo tự động chảy ra một lượng gạo cho người đó nhận. Thời gian phục vụ một người phụ thuộc vào tốc độ thao tác của người đó.

Có \(n\) người đang xếp hàng trước cây ATM gạo (tất nhiên họ đứng cách nhau tối thiểu \(2m\)). Những người này được đánh số từ \(1\) đến \(n\) theo thứ tự xa dần cây ATM. Cây ATM có thể phát \(1\) hoặc \(2\) túi gạo mỗi lần, thời gian phục vụ phụ thuộc vào tốc độ thao tác của người lấy gạo. Theo đó, người thứ \(i\) sẽ mất \(a_i(s)\) để rút \(1\) túi gạo, và \(b_i(s)\) để rút \(2\) túi. Theo qui định mỗi người chỉ được lấy \(1\) túi thôi, nhưng họ có thể rút \(2\) túi và chia cho người đứng ngay phía sau, sau đó cả hai người rời khỏi hàng.

Yêu cầu: Với phương châm sẽ không có ai bị bỏ lại, chúng ta cần phục vụ người dân nhanh nhất có thể. Giả sử biết thông tin về thời gian thao tác của mỗi người, hãy tính tổng thời gian phục vụ ít nhất có thể. Biết rằng thời gian chuyển đổi phục vụ giữa hai người là không đáng kể.

Input

• Dòng đầu chứa số nguyên dương: \(n\)
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương: \(a_i, b_i\) (\(1 \leq a_i \leq b_i \leq 10^9\))

Output

• Dòng đầu ghi tổng thời gian phục vụ nhỏ nhất tìm được.
• Dòng thứ hai ghi \(n\) số tự nhiên, số thứ \(i\) là số túi gạo mà người thứ \(i\) rút ra từ cây.

Nếu có nhiều phương án đều tốt nhất, in ra phương án có thứ tự từ điển nhỏ nhất (tức dãy tạo bởi số túi gạo của \(n\) người rút theo thứ tự từ \(1\) đến \(n\) có thứ tự từ điển nhỏ nhất).

Example

4
3 3
1 1
2 5
10 11

8
2 0 2 0

4
3 3
1 1
2 5
3 4

7
1 2 0 1

Scoring

• Có \(50\%\) số test với \(1 \leq n \leq 20\).
• Có \(50\%\) số test với \(20 < n \leq 10^5\).