Nhân dịp Tết thiếu nhi ngày 1-6, Công đoàn của công ty VHP sẽ tổ chức phát quà cho các con của cán bộ công nhân viên trong công ty có thành tích học tập tốt. Họ muốn phát ~k~ phần quà. Mỗi phần quà đều có một bó hoa, một hộp bút, một quyển vở. Hiện tại, Công đoàn đã chuẩn bị được:

• ~a~ bó hoa,
• ~b~ hộp bút,
• ~c~ quyển vở.

Yêu cầu

Tính số lượng tối thiểu các món đồ mà Công đoàn cần chuẩn bị thêm để đảm bảo có đủ ~k~ phần quà.

Dữ liệu đầu vào

Gồm một dòng gồm bốn số nguyên ~a, b, c, k~ ~(1 \le a, b, c, k \le 1000)~ tương ứng là số bó hoa, số hộp bút, số quyển vở, số phần quà.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số món đồ cần chuẩn bị thêm.

Ví dụ

Ví dụ 1

INPUT

2 3 5 4

OUTPUT

3

Giải thích:

• Có ~2~ bó hoa, ~3~ hộp bút, ~5~ quyển vở nên chúng ta có ~2~ phần quà.
• Chúng ta cần có thêm ~2~ bó hoa, ~1~ hộp bút nữa để tổng số là ~4~ phần quà.
• Số món đồ cần chuẩn bị thêm là: ~2 + 1 = 3~.

Gần nhà Bờm có một ga tàu điện. Tại ga này, hàng ngày, chuyến tàu điện đầu tiên sẽ dừng đón khách tại thời điểm ~T_0~, chuyến thứ hai dừng đón khách tại thời điểm ~T_0 + D~, chuyến thứ ba dừng tại thời điểm ~T_0 + 2 \times D~, ... Có ~N~ hành khách thường xuyên chờ tàu điện tại ga. Hành khách thứ ~i~ đến ga tàu tại thời điểm ~s_i~ và sẽ lên chuyến tàu đầu tiên đến ga ở thời điểm không sớm hơn ~s_i~.

Yêu cầu

Cho ~T_0~, ~D~ và thời điểm các hành khách đến ga. Hãy xác định số hiệu chuyến tàu điện của từng hành khách sẽ lên, giả sử thời gian lên xuống xe của mỗi hành khách là không đáng kể.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa ba số nguyên ~N, D, T_0~ ~(2 \le N \le 10^4; 1 \le D \le 10^4; 0 \le T_0 \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~s_1, s_2, \ldots, s_N~ ~(0 \le s_i \le 10^6)~.

Dữ liệu đầu ra

Gồm một dòng chứa ~N~ số nguyên, số thứ ~i~ là số hiệu chuyến tàu điện mà hành khách thứ ~i~ sẽ lên.

Ví dụ

Ví dụ 1

INPUT

3 5 8
0 15 23

OUTPUT

1 3 4

Giải thích:

• Hành khách đầu tiên đón được chuyến tàu thứ ~1~ ở thời điểm ~8~.
• Hành khách thứ ~2~ đón được chuyến tàu thứ ~3~ ở thời điểm ~18~.
• Hành khách thứ ~3~ đón được chuyến tàu thứ ~4~ ở thời điểm ~23~.

Nhân dịp Tết thiếu nhi ngày 1-6, Bờm và Cuội nhận được ~2N~ đồ chơi, các đồ chơi có giá trị đôi một khác nhau, thuộc phạm vi từ ~1~ đến ~2N~. Đồ chơi của Bờm có giá trị ~a_1, a_2, a_3, \ldots, a_N~, đồ chơi của Cuội có các giá trị còn lại. Hai bạn cùng rủ nhau chơi một trò chơi như sau:

• Hai người lần lượt chọn một đồ chơi cho từng ván, mỗi người chỉ dùng mỗi đồ chơi đúng một lần.
• Người có đồ chơi có giá trị lớn hơn thì thắng ván đó.

Yêu cầu

Hỏi trong trường hợp may mắn nhất, Bờm có thể thắng bao nhiêu ván?

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

• Dòng đầu tiên: Ghi một số nguyên ~N~ ~(1 \le N \le 50000)~.
• ~N~ dòng tiếp theo: Mỗi dòng ghi ~1~ số nguyên ~a_i~ ~(1 \le a_i \le 2N)~, là giá trị các đồ chơi Bờm có.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số ván nhiều nhất mà Bờm có thể thắng.

Ràng buộc dữ liệu

• Subtask 1 (50% điểm): ~N \le 100~.
• Subtask 2 (50% điểm): ~N \le 50000~.

Ví dụ

Ví dụ 1

INPUT

3
1
5
4

OUTPUT

2

Giải thích:

• Ván ~1~: Bờm chọn đồ chơi có giá trị ~1~, Cuội chọn đồ chơi có giá trị ~6~ (Cuội thắng).
• Ván ~2~: Bờm chọn đồ chơi có giá trị ~5~, Cuội chọn đồ chơi có giá trị ~2~ (Bờm thắng).
• Ván ~3~: Bờm chọn đồ chơi có giá trị ~4~, Cuội chọn đồ chơi có giá trị ~3~ (Bờm thắng).

Hai bạn Bờm và Cuội lại rủ nhau chơi trò chơi thứ hai như sau: Các bạn có ~n~ bảng số nguyên được đánh số từ ~1~ đến ~n~, mỗi bảng mang một số nguyên dương là số điểm mà các bạn nhận được khi chọn bảng đó. Trò chơi được chia thành ~k~ lượt chơi (~k = \frac{n}{2}~ nếu ~n~ chẵn, ~k = \frac{n+1}{2}~ nếu ~n~ lẻ).

Tại lượt chơi thứ ~i~, các bạn cần chọn ra ~i~ bảng số sao cho tổng điểm là lớn nhất và không được chọn đồng thời hai bảng số nào có số thứ tự liên tiếp nhau. Sau khi hoàn thành mỗi lượt chơi các bạn phải trả lại các bảng số đã chọn về vị trí cũ để phục vụ lượt chơi tiếp theo.

Yêu cầu

Hãy lập trình chương trình giải quyết bài toán trên.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất gồm một số nguyên dương ~n~ ~(1 \le n \le 200000)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_i~ ~(1 \le a_i \le 10^9)~ là số điểm của mỗi bảng số.

Dữ liệu đầu ra

Gồm ~k~ dòng, dòng thứ ~i~ ghi ra điểm tối đa mà bạn Bờm và Cuội có thể đạt được tại lượt ~i~.

Ràng buộc dữ liệu

• Subtask 1 (16% điểm): ~n \le 20~.
• Subtask 2 (16% điểm): ~n \le 2000; a_1 = a_2 = \ldots = a_{n - 1} = a_n~.
• Subtask 3 (18% điểm): ~n \le 2000~.
• Subtask 4 (50% điểm): Không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

5
1 6 4 9 8

OUTPUT

9
15
13

Giải thích:

• Lượt ~1~ chọn vị trí: ~4~.
• Lượt ~2~ chọn vị trí: ~2~ và ~4~.
• Lượt ~3~ chọn vị trí: ~1~, ~3~ và ~5~.