Tổng chính xác (Exact Sum)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Peter có một số tiền $M$ và muốn dùng toàn bộ số tiền đó để mua đúng hai quyển sách.

Có $n$ quyển sách, quyển thứ $i$ có giá $p_i$.

Hãy chọn hai quyển khác nhau có giá lần lượt là $a$ và $b$ sao cho:

với $a\le b$.

Nếu có nhiều cặp thỏa mãn, hãy chọn cặp có độ chênh lệch giá nhỏ nhất:

là nhỏ nhất.

Đề bảo đảm luôn tồn tại ít nhất một cặp hợp lệ.

Input

Dòng đầu chứa $n$.

Dòng thứ hai chứa $n$ số nguyên $p_1,p_2,\ldots,p_n$, là giá của $n$ quyển sách.

Dòng thứ ba chứa số tiền $M$.

Output

In đúng theo mẫu:

Peter should buy books whose prices are a and b.

Sau dòng kết quả có một dòng trống.

Subtask

• Subtask 1 — 20%: $2\le n\le100$.
• Subtask 2 — 30%: $2\le n\le2000$.
• Subtask 3 — 50%: $2\le n\le10000$, mỗi giá sách nhỏ hơn $1000001$; luôn tồn tại lời giải.

Ví dụ

Input

5
10 2 6 8 4
10

Output

Peter should buy books whose prices are 4 and 6.

Giải thích

Các cặp có tổng bằng $10$ gồm $(2,8)$ và $(4,6)$. Ta có:

trong khi:

Vì $2<6$, cặp $(4,6)$ là đáp án.