Nguồn: Học sinh Giỏi THPT Hà Nội năm 2011 - 2012

Một công ty đặt kế hoạch tham gia \(N\) dự án. Các dự án được đánh số từ \(1\) đến \(N\). Để thực hiện dự án thứ \(i\) công ty cần có số vốn lớn hơn hoặc bằng \(V_i\) (\(1 \le i \le N\)). Sau khi thực hiện dự án thứ \(i\), công ty sẽ thu hồi được vốn bỏ ra và có thêm lợi nhuận \(L_i\). Ban đầu công ty có số vốn \(S\). Công ty có thể thực hiện lần lượt \(N\) dự án theo một thứ tự tùy ý.

Yêu cầu: Hãy xác định số lượng lớn nhất các dự án mà công ty có thể thực hiện đươc?

Input

Dữ liệu vào từ tệp văn bản BAI1.INP:

• Dòng đầu chứa hai số nguyên dương \(N\) và \(S, 1 \le N \le 10^3, 1 \le S \le 10^6\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le N\)) chứa hai số nguyên dương \(V_i\) và \(L_i\) không vượt quá \(10^6\).

Output

Kết quả ra tệp văn bản BAI1.OUT:

• Số lượng lớn nhất các dự án mà công ty có thể thực hiện đươc.

Examples

5 2
25 19
1 1
1 2
5 5
10 12

4

5 2
25 19
3 1
6 3
5 3
12 10

0

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2011 - 2012

Một dãy dấu ngoặc hợp lệ là một dãy các ký tự "(" và ")" được định nghĩa như sau:

• Dãy rỗng (không có ký tự nào) là một dãy dấu ngoặc hợp lệ
• Nếu \(A\) là một dãy dấu ngoặc hợp lệ thì \((A)\) là dãy dấu ngoặc hợp lệ. Dấu ngoặc mở và dấu ngoặc đóng hai bên dãy \(A\) được gọi là tương ứng với nhau
• Nếu \(A\) và \(B\) là hai dãy dấu ngoặc hợp lệ thì \(AB\) là dãy dấu ngoặc hợp lệ.

Ban đầu có một dãy dấu ngoặc hợp lệ, người ta viết vào dưới mỗi dấu ngoặc mở một số là số dấu ngoặc (cả đóng và mở) nằm giữa dấu ngoặc mở đó và dấu ngoặc đóng tương ứng. Sau đó xoá đi dãy ngoặc.

Ví dụ: \(((()))(())()()\) là một dãy dấu ngoặc hợp lệ. Các dấu ngoặc mở ở các vị trí: \(1, 2, 3, 7, 8, 11, 13\) tương ứng lần lượt với các dấu ngoặc đóng ở các vị trí: \(6, 5, 4, 10, 9, 12, 14\). Có thể viết các số dưới các dấu ngoặc mở của dãy như sau:

 (  (  (  )  )  )  (  (  )  )  (  )  (  )

 4 2 0        2 0       0    0

Yêu cầu: Cho biết dãy số còn lại, hãy khôi phục lại dãy ngoặc ban đầu.

Input

Dữ liệu vào từ tệp văn bản BAI2.INP:

• Dòng \(1\): Ghi số \(N\) là số phần tử của dãy số còn lại (\(N ≤ 10000\))
• Dòng \(2\): Ghi lần lượt các số trong dãy

Output

Kết quả ra tệp văn bản BAI2.OUT:

• Gồm 1 dòng ghi dãy dấu ngoặc khôi phục được.

Examples

7
4 2 0 2 0 0 0

((()))(())()()

10
8 2 0 0 0 4 0 0 0 0

((())()())(()())()()

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2011 - 2012

Số nguyên dương \(U_1\) có thể biểu diễn dưới dạng tích của hai số nguyên dương \(X, Y\) với \(X \le Y\). Nếu thay \(X\) bởi \(X - 1\) còn \(Y\) bởi \(Y + 1\) thì nhận được số nguyên mới \(U_2 = (X - 1) \times (Y + 1)\). Bằng phép biến đổi như trên đối với \(U_2\) nhận được \(U_3\). Quá trình trên sẽ dừng nếu gặp số \(0\). Như vậy ta nhận được dãy các số nguyên dương \(U_1 > U_2 > ... > U_k > 0\).

Ví dụ: \(U_1 = 12\) có \(3\) cách phân tích \(1 \times 12, 3 \times 4, 2 \times 6\). Với cách phân tích thứ hai nhận được số mới \(U_2 = (3 - 1) \times (4 + 1) = 10\). Với \(10 = 2 \times 5\) nhận được \(U_3 = (2 -1) \times (5 + 1) = 6\). Với \(6 = 1 \times 6\) nhận được số \(0\). Số lượng các số nguyên dương theo các biến đổi trên là \(k = 3\).

Yêu cầu: Cho trước số nguyên dương \(N\) (\(1 \le N \le 10000\)), tìm cách biến đổi sao cho dãy các số nguyên dương nhận được từ \(N\) có nhiều số hạng nhất.

Input

Dữ liệu vào từ tệp văn bản BAI3.INP:

• Chứa số nguyên dương \(N\).

Output

Kết quả ra tệp văn bản BAI3.OUT:

• Dòng đầu tiên ghi \(K\) là số lượng số nguyên dương tìm được.
• \(K\) dòng tiếp theo dòng thứ \(i\) ghi hai số \(X, Y\) là cách biểu diễn của số \(U_i\) (\(1 \le i \le k\)). Nếu có nhiều cách biểu diễn chỉ đưa ra cách biểu diễn với \(X\) nhỏ nhất.

Examples

12

5
3 4
2 5
2 3
2 2
1 3

13

1
1 13