Xét bài toán: Cho n phân số a1/b1 ,…,an/bn (ai,bi nguyên dương), hãy tìm dãy chỉ số 1 ≤ i1 < i2 <⋯< ik ≤ n sao cho a (i1) / b (i1) < a (i2) / b (i2 ) <⋯< a (ik) / b (i_k) và k lớn nhất có thể.

Bài toán trên được mở rộng như sau: Có thể đảo lại một phân số nếu muốn (phân số ai / bi đảo lại thành phân số bi / ai ), sau đó tìm dãy chỉ số thỏa mãn đề bài mà k lớn nhất có thể.

Yêu cầu: Cho n phân số và số nguyên w, trong đó 𝑤 = 0 nghĩa là không được phép đảo bất kỳ một phân số nào (bài toán ban đầu) hoặc 𝑤 = 1 nếu được phép đảo không quá một phân số (bài toán mở rộng), hãy đưa ra giá trị 𝑘 lớn nhất có thể.

Dữ liệu: Vào từ tệp văn bản FRACTION.INP theo khuôn dạng:

Dòng đầu ghi hai số nguyên n,w(1≤n≤10^3;0≤w≤1);
Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên dương a_i,b_i lần lượt là tử số và mẫu số của phân số thứ i (1≤i≤n,〖0<a〗_i,b_i≤10^9).

Kết quả: Ghi ra tệp văn bản FRACTION.OUT một số nguyên duy nhất là giá trị k lớn nhất tìm được.

Ví dụ:

FRACTION.INP    FRACTION.OUT
4 0             2
5 1
1 3
3 2
1 2 


4 1             3
5 1
1 3
3 2
1 2

Ràng buộc:

• Có 25% số test ứng với 25% số điểm của bài thỏa mãn: n≤10,w=0;
• Có 25% số test ứng với 25% số điểm của bài thỏa mãn: n≤10,w=1;
• Có 25% số test ứng với 25% số điểm của bài thỏa mãn: 10<n≤10^3,w=0; </li>
• Có 25% số test ứng với 25% số điểm của bài thoả mãn: 10<n≤10^3,w=1.</li>