Mandink đang đặt vé một chuyến tàu hỏa đi Đà Nẵng. Tuy nhiên vì thời tiết xấu, chiếc xe lửa phải chạy chậm hơn để đảm bảo an toàn cho hành khách. Mandink lên tàu và xuất phát ở thời điểm ~0~ tại ga CLA, đi qua ~N~ ga tàu theo thứ tự ~1, 2,.., N~ và dừng chân ở ga thứ ~N~ - điểm đến của Mandink.

Sau khi tìm hiểu lịch trình của tàu, Mandink đã ghi lại được ~N~ cặp số ~(a_i , b_i)~. Trong đó, ~a_i~ là thời điểm dự kiến để tàu đến ga thứ ~i~, và ~b_i~ là thời điểm dự kiến để tàu rời ga thứ ~i~.

Đồng thời, với kiến thức uyên thâm và những thông tin thu thập được từ ga tàu, Mandink có thể tính được ~N~ giá trị nguyên ~tm_1, tm_2, ..., tm_N~. Trong đó, ~tm_i~ là thời gian delay mà tàu cần để đi từ ga thứ ~i − 1~ đến ga thứ ~i~. Như vậy, tàu cần tổng cộng ~a_i − b_{i − 1} + tm_i~ để đi từ ga ~i-1~ đến ga ~i~ (nếu ~i = 1~ thì ~b_0~ là thời điểm tàu rời ga CLA, và nó bằng ~0~).

Tàu sẽ rời ga thứ ~i~, nếu cả hai điều kiện sau đều thỏa:

1. Tàu ở đã ở ga thứ ~i~ ít nhất là ~\frac{b_i−a_i}{2}~ (chia làm tròn lên) đơn vị thời gian, để tàu có thời gian trả và nhận hành khách.
2. Thời điểm hiện tại ~≥ b_i~.

Vì Mandink đã dùng hết chất xám để thu thập thông tin, các bạn hãy giúp Mandink tính toán thời điểm tàu sẽ đến ga thứ ~N~ nhé.

Dữ liệu vào

• Dòng đầu tiên ghi một số nguyên ~N~ ~(1 ≤ N ≤ 100)~ là số ga mà tàu sẽ đi qua.
• ~N~ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương: ~a_i~ và ~b_i~ ~(1 ≤ a_i < b_i ≤ 10^6 )~. Dữ liệu vào đảm bảo ~b_i < a_{i+1}~.
• Dòng tiếp theo ghi ~N~ số nguyên ~tm_1, tm_2, ..., tm_N~ ~(0 ≤ tm_i ≤ 10^6 )~.

Dữ liệu ra

• In ra một số nguyên là thời điểm Mandink đến ga ~N~.

Sample Input 1

2
2 4
10 12
0 2

Sample Output 1

12

Sample Input 2

5
1 4
7 8
9 10
13 15
19 20
1 2 3 4 5

Sample Output 2

32

Giải thích

• Trong testcase đầu tiên, Mandink đến ga ~1~ mà không có bất kỳ sự delay nào tại thời điểm ~a_1 = 2~ (vì ~tm_1 = 0~). Sau đó, Mandink khởi hành tại thời điểm ~b_1 = 4~. Cuối cùng, Mandink đến trạm ~2~ với thời gian delay là ~tm_2 = 2~, tức là vào lúc ~12~.
• Trong testcase thứ hai, Mandink đến ga ~1~ với thời gian delay ~tm_1 = 1~, tức tại thời điểm ~2~. Đồng thời, đoàn tàu phải ở lại ga ít nhất ~\frac{b_1−a_1}{2} = 2~
  đơn vị thời gian và phải khởi hành không sớm hơn lúc ~b_1 = 4~. Kết quả là đoàn tàu khởi hành đúng lúc ~4~ giờ. Tương tự, chúng ta có thể tính được rằng đoàn tàu đến ga thứ hai vào lúc ~9~ và khởi hành vào lúc ~10~; ở nhà ga thứ ba: đến lúc ~14~ giờ và khởi hành lúc ~15~ giờ; ở trạm thứ tư: đến lúc ~22~ và khởi hành lúc ~23~. Và cuối cùng, đến trạm thứ năm lúc ~32~.