Xét bài toán: Cho \(n\) phân số \(\frac{a_{1}}{b_{1}},\ldots,\frac{a_{n}}{b_{n}}\) \((a_{i},b_{i}\ \)nguyên dương), hãy tìm dãy chỉ số

\(1 \leq i_{1} < i_{2} < \ldots < i_{k} \leq n\ \)sao cho \(\frac{a_{i_{1}}}{b_{i_{1}}} < \frac{a_{i_{2}}}{b_{i_{2}}} < \ldots < \frac{a_{i_{k}}}{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ố \(\frac{a_{i}}{b_{i}}\) đảo lại thành phân số \(\frac{b_{i}}{a_{i}}\)), 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:

+ Dòng đầu ghi hai số nguyên \(n,w(1 \leq n \leq 10^{3};0 \leq w \leq 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 \leq i \leq n,{0 < a}_{i},b_{i} \leq 10^{9})\).

Kết quả: Ghi một số nguyên duy nhất là giá trị \(k\) lớn nhất tìm được.

Ví dụ:

Ràng buộc:

• Có \(25\%\) số test ứng với \(25\%\) số điểm của bài thỏa mãn: \(n \leq 10,w = 0\);

• Có \(25\%\) số test ứng với \(25\%\) số điểm của bài thỏa mãn: \(n \leq 10,w = 1\);

• Có \(25\%\) số test ứng với \(25\%\) số điểm của bài thỏa mãn: \(10 < n \leq 10^{3},w = 0\);

• Có \(25\%\) số test ứng với \(25\%\) số điểm của bài thoả mãn: \(10 < n \leq 10^{3},w = 1\).