~Tahp~ là một người rất thích số đẹp. ~Tahp~ định nghĩa một số nguyên dương là đẹp nếu số đó chia hết cho ~2~ và có tổng các chữ số ở biểu diễn thập phân chia hết cho ~9~.

Yêu cầu: cho số nguyên ~N~, hãy giúp Tahp tìm số nguyên dương đẹp thứ ~N~.

Input

• Gồm ~1~ dòng chứa một số nguyên ~N~ ~(1 \le N \le 10^7)~.

Output

• In ra số đẹp thứ ~N~.

Sample Input

3

Sample Output

54

Nhân dịp quốc tế thiếu nhi ~1~/~6~, nhà trường tổ chức phát kẹo cho học sinh. Để màn phát kẹo thêm phần hấp dẫn, lớp của ~Egg~ có một trò chơi nho nhỏ:

Cho dãy gồm ~n~ số nguyên dương, ~Egg~ được phép sắp xếp thứ tự các số trong dãy tuỳ ý. Số kẹo nhận được sẽ bằng tổng độ dài của các dãy con tăng ngặt dài nhất (không cần liên tiếp) kết thúc tại ~i~ với mọi ~1 \le i \le n~.

~Egg~ muốn nhận được số kẹo lớn nhất. Hãy giúp ~Egg~ nhé!

Input

• Dòng thứ nhất chứa số nguyên ~n~ là số lượng số trong dãy. (~1 \le N \le 2 \times 10^5~)

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~, mỗi số được ngăn cách nhau bởi một dấu cách. (~a_i \le 10^9~)

Output

• Ghi ra số kẹo lớn nhất ~Egg~ có thể lấy được.

Sample Input

3
1 3 2

Sample Output

6

Note

Giải thích test mẫu:

~Egg~ sẽ sắp xếp dãy các gói kẹo thành dãy ~\{1, 2, 3\}~.

Gọi ~f_i~ là độ dài của dãy con tăng ngặt dài nhất kết thúc tại ~i~, ta có ~f = \{1, 2, 3\}~.

Tổng độ dài các dãy con tăng ngặt dài nhất kết thúc tại ~i~ với mọi ~1 \le i \le n~ là ~6~, đây cũng là giá trị lớn nhất có thể đạt được.

Có ~n + 1~ ngọn núi, ngọn núi thứ ~i~ (~1 \le i \le n~) có độ cao ~h_i~. Có ~n~ con mèo đang sống, chú mèo ~i~ nằm ở ngọn núi ~i~, ngọn núi thứ ~n + 1~ có độ cao lớn nhất trong mọi hang (không có con mèo nào sống ở đó). Mỗi ngày những con mèo đều phải tập thể dục theo một quy luật cho trước, con mèo ~i~ sẽ thức hiện ~J_i~ lần nhảy, mỗi lần nhảy con mèo sẽ nhảy qua ngọn núi gần nhất cao hơn và có chỉ số lớn hơn chỉ số ngọn núi hiện tại nó đang đứng. Khi con mèo đã nhảy đến ngọn núi ~n + 1~ thì không thực hiện nhảy tiếp nữa.

Yêu cầu: Hãy xác định độ cao của ngọn núi mà mỗi con mèo sẽ đến sau khi tập thể dục xong (một ngon núi có thể chứa nhiều con mèo). Nếu vị trí mới của con mèo là ngọn núi ~n + 1~ thì ghi ~-1~.

Input:

• Dòng thứ nhất chứa số nguyên dương ~n~ (~1 \le n \le 10 ^ 6~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~h_1~, ~h_2~, …, ~h_n~ (~1 \le h_i \le 10 ^ 6~).
• Dòng thứ ba chứa ~n~ số nguyên dương ~J_1, J_2, … J_n~ (~1 \le J_i~ < ~10^6~).

Output:

• Một dòng chứa ~n~ số nguyên là độ cao nơi ở mới của mỗi chú mèo.

Sample Input:

5 
3 6 7 6 4 
2 1 1 3 2 

Sample Output:

7 7 -1 -1 -1

Giải thích:

• Mèo đầu tiên nhảy ~2~ lần từ ngọn núi ~1 \rightarrow 2 \rightarrow 3~.
• Mèo thứ hai nhảy ~1~ lần từ ~2 \rightarrow 3~.
• Mèo thứ ba nhảy ~1~ lần từ ~3 \rightarrow 6 (n + 1)~ nên in ra ~-1~.
• Mèo thứ tư nhảy ~1~ lần từ ~4 \rightarrow 6 (n + 1)~ nên in ra ~-1~.
• Mèo thứ năm nhảy ~1~ lần từ ~5 \rightarrow 6 (n + 1)~ nên in ra ~-1~.

Subtask:

• ~20\%~ số test có ~n \le 20~.
• ~20\%~ số test tiếp theo có ~J_i \le 10~
• ~60\%~ số test còn lại không có điều kiện gì thêm.

~Neko~ rất thích mua sắm, thành phố ~Neko~ đang sống có ~1~ chuỗi ~n~ cửa hàng. Chuỗi cửa hàng có thể mô tả bằng một dãy số, mỗi cửa hàng có tọa độ ~x_1~, ~x_2~, ... ~x_N~. Trên chuỗi có ~N + 2~ ga tàu lửa, mỗi cửa hàng đều có một ga tàu lửa, ngoài ra còn một ga nằm ở tọa độ ~0~ và một trạm nằm ở tọa độ ~L~.

Ở thời gian ~0~, tàu khởi hành từ ga ~0~ theo chiều dương. Đoàn tàu đi với vận tốc ~1~ đơn vị/giây. Tại thời điểm ~L~, tàu sẽ đến ga cuối cùng ở tọa độ ~L~. Khi đó tàu sẽ ngay lập tức quay đầu đi ngược chiều với cùng vận tốc theo chiều âm. Tại thời điểm ~2L~, đoàn tàu sẽ đến ga ~0~ và ngay lập tức lại quay ngược lại theo chiều dương. Quá trình này lặp lại vô hạn.

Khi tàu đến ga có ~Neko~, ~Neko~ có thể lên (nếu không ở trên tàu) hoặc rời tàu (nếu ở trên tàu) ngay lập tức. Tại thời điểm ~0~, Neko đang ở nhà ga ~0~.

~Neko~ muốn đi mua sắm ở tất cả ~N~ cửa hàng (đi theo thứ tự lần lượt từ ~1~ đến ~N~). ~Neko~ tốn ~t_i~ giây để mua sắm trong cửa hàng có tọa độ ~x_i~ trước khi chuyển sang cửa hàng tiếp theo. Để chuyển sang cửa hàng tiếp theo thì tất nhiên ~Neko~ phải bắt xe lửa. ~Neko~ có thể lên tàu ngay lập tức sau khi mua sắm xong (nếu vị trí của tàu trùng với tọa độ ga ~Neko~ đang đứng) hoặc phải chờ cho đến khi tàu đến.

Hãy tìm thời gian tối thiểu để ~Neko~ hoàn thành việc mua sắm của mình và trở về nhà tại ga ~0~.

Input

• Dòng đầu chứa ~2~ số nguyên ~N~ và ~L~ cách nhau bởi ~1~ dấu cách. ~(1 \le N \le 300000, 1 \le L \le 10^9)~
• Dòng tiếp theo chứa dãy số ~x_1~, ~x_2, \dots ,x_N~, dữ liệu đảm bảo tọa độ của các cửa hàng phân biệt. ~(0 < x_i < L)~
• Dòng cuối cùng chứa dãy số ~t_1~, ~t_2, \dots ,t_N~ ~(1 \le t_i \le 10^9)~

Output

• Ghi ra thời gian tối thiếu (tính bằng giây) để ~Neko~ hoàn tất việc mua sắm của mình và trở về nhà tại ga ~0~.

Sample Input

2 10 
5 8 
10 4

Sample Output

40

Subtask

• ~30\%~ số test có ~N \le 100, L \le 1000, t_i \le 1000~
• ~70\%~ số test còn lại không có điều kiện gì thêm

~illya~ và ~nkwn~ chơi một trò chơi với dãy số ~a~. Hai bạn sẽ lần lượt thực hiện các lượt chơi, tại mỗi lượt một bạn sẽ lấy ra khỏi dãy phần tử đầu tiên hoặc phần tử cuối cùng và cộng giá trị phần tử đó vào số điểm của mình. Trước khi bắt đầu chơi, ~illya~ được quyền sắp xếp dãy ~a~ theo thứ tự tùy ý và ~nkwn~ là người chơi trước.

Số điểm ban đầu của mỗi bạn là ~0~ và cả hai đều chơi tối ưu để điểm của mình là lớn nhất. Cho dãy ~a~, hãy tìm số điểm của ~illya~ và ~nkwn~ sau khi trò chơi kết thúc.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ - số phần tử của dãy ~a~ (~n \leq 100~).

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, a_3, \dots, a_n~ (~1 \leq a_i \leq 10^4~).

Output

• In ra hai số trên cùng một dòng lần lượt là số điểm của ~illya~ và ~nkwn~ sau khi trò chơi kết thúc.

Sample Input 1

3
1 2 3

Sample Output 1

3 3

Sample Input 2

4
1 2 3 4

Sample Output 2

5 5

Subtask

• ~30\%~ số test có ~n \leq 20~.
• ~50\%~ số test khác có ~n \leq 50~.
• ~20\%~ còn lại không có ràng buộc thêm.

Có ~N~ công việc, công việc thứ ~i~ có thời hạn deadline ~d_i~ và số điểm ~p_i~. Để lấy được số điểm ~p_i~, bạn phải hoàn thành công việc thứ ~i~ ở thời điểm không trễ hơn deadline ~d_i~.

Hãy tìm cách lấy số điểm lớn nhất nếu thực hiện ~k~ công việc đầu tiên với mọi ~k~ từ ~1~ đến ~N~.

Chú ý: Coi thời điểm bắt đầu thực hiện các công việc là thời điểm ~0~ và thời gian hoàn thành mỗi công việc đều là ~1~ đơn vị thời gian.

Input

• Dòng đầu tiên chứa số ~N~ (~N \le 10^5~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ~2~ số nguyên là ~d_i~ và ~p_i~ cách nhau bởi một dấu cách. (~1 \le d_i, p_i \le 10^6~)

Output

• Ghi ra ~N~ dòng, dòng thứ ~i~ là số điểm lớn nhất có thể lấy được nếu thực hiện ~i~ công việc đầu tiên.

Sample Input

4
4 20
1 10
1 40
1 30

Sample Output

20
30
60
60

Subtask

• ~20\%~ số test có ~N \le 10~
• ~20\%~ số test tiếp theo có ~N \le 1000~
• ~60\%~ số test còn lại không có điều kiện gì thêm