Vào ngày sinh nhật, hoangduong nhận được món quà gồm ~n~ viên ngọc, mỗi viên ngọc có màu là một trong ~c~ màu. hoangduong muốn ghép đôi các viên ngọc sao cho mỗi cặp gồm hai viên ngọc khác màu.

Hãy tìm một phương án ghép cho hoangduong, dữ liệu đảm bảo luôn có nghiệm.

INPUT

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~c~ (~2 \le n \le 10^5~, ~n~ chia hết cho ~2~, ~1 \le c \le n~)

• Dòng thứ hai gồm ~c~ số nguyên là số viên ngọc của mỗi màu ~1, 2, ..., c~

OUTPUT

In ra ~n/2~ dòng, mỗi dòng ghi cặp số nguyên ~u, v~ chỉ một cặp gồm một ngọc màu ~u~ và một ngọc màu ~v~

Nếu có nhiều cách chọn thoả mãn thì in ra cách bất kỳ

SAMPLE INPUT

8 3
2 2 4

SAMPLE OUTPUT

1 3
1 3
2 3
2 3

hoangduong có ~n~ cuốn sách (~1 \le n \le 2000~), và hoangduong muốn xây một kệ sách gồm nhiều tầng để chứa tất cả các cuốn sách này.

Mỗi cuốn sách có chiều rộng ~w_i~ và chiều cao ~h_i~. Các cuốn sách cần được bỏ vào các tầng kệ sách theo thứ tự. Ví dụ như tầng thứ nhất cần bỏ các cuốn sách từ ~1~ đến ~k~, tầng thứ ~2~ sẽ bắt đầu từ cuốn sách thứ ~k + 1~, và cứ thế tiếp tục. Mỗi tầng kệ sách có chiều rộng tối đa là ~L~ (~1 \le L \le 10^9~). Chiều cao của mỗi tầng kệ sách bằng với chiều cao của cuốn sách có chiều cao lớn nhất, và chiều cao của cả kệ sách bằng với tổng chiều cao của mỗi tầng kệ sách khi xếp dọc lên (bỏ qua tấm gỗ ngăn cách giữa các tầng kệ sách).

Hãy giúp hoangduong tính chiều cao thấp nhất có thể của cả kệ sách khi xếp chồng lên nhau.

INPUT

Dòng 1: Gồm hai số tự nhiên cách nhau là ~n~ và ~L~.

~n~ dòng tiếp theo mỗi dòng chứa hai số tự nhiên cách nhau là ~h_i~ và ~w_i~. (~1 \le h_i \le 10^9~, ~1 \le w_i \le L~).

OUTPUT

Một dòng duy nhất chứa chiều cao nhỏ nhất của cả kệ sách.

SAMPLE INPUT

5 10
5 7
9 2
8 5
13 2
3 8

SAMPLE OUTPUT

21

Giải thích: Có ba tầng, tầng đầu tiên chứa cuốn sách thứ nhất (chiều cao là ~5~ và chiều rộng là ~7~), tầng thứ hai chứa cuốn thứ ~2~ đến cuốn thứ ~4~ (chiều cao là ~13~, chiều rộng là ~9~), và tầng chứa cuốn sách thứ ~5~ (chiều cao là ~3~, chiều rộng là ~8~).