Farmer John già trở nên cáu và đa nghi. Quên đa dạng bò giúp trại phát triển nhiều năm, dựng hàng rào lớn cản láng giềng và cấm hẳn vài trại. Bò buồn: không thăm bạn, hủy Olympic Vắt Sữa Quốc Tế chờ cả năm.

Cả láng giềng được phép cũng khó: cổng duy nhất hỏi nghiêm từng con tạo hàng dài.

Với $N$ bò biết thời gian tới và trả lời. Chỉ một cùng lúc, tới gần nhau đợi lần lượt. Tới5 mất7 khiến con tới8 chờ12.

Tìm thời gian sớm nhất tất cả vào.

Dữ liệu vào

Dòng đầu $N$, nguyên dương tối đa100. Sau $N$ dòng tới và thời gian hỏi, mỗi nguyên dương tối đa1,000,000.

Dữ liệu ra

Ít nhất thời gian xử lý xong tất cả.

Ví dụ

Dữ liệu vào 1

3
2 1
8 3
5 7

Dữ liệu ra 1

15

Ghi chú

Đầu tới2 xử lý nhanh, cổng rảnh tới con thứ3 lúc5. Con thứ2 tới8 đợi $5+7=12$, xong $12+3 = 15$.

Tác giả bài toán: Brian Dean