{"code":"fraction","name":"fraction","description":"Xét bài toán với $n$ phân số $\\frac{a_1}{b_1}, \\frac{a_2}{b_2}, ..., \\frac{a_n}{b_n}$ ($a_i, b_i$ nguyên dương), hãy tìm dãy chỉ số $1 < i_1 < i_2 < ... < i_k \\le n$ sao cho $\\frac{a_1}{b_1} < \\frac{a_2}{b_2} < ... < \\frac{a_k}{b_k}$ mà $k$ lớn nhất.\r\n\r\nBài toán trên được mở rộng như sau: Hãy tìm cách đả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 $\\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ể.\r\n\r\n**Yêu cầu:** Cho $n$ phân số và số nguyên $w$ trong đó $w = 0$ nghĩa là không được phép đảo bất kì phân số nào (bài toán ban đầu) hoặc $w = 1$ nếu được đảo không quá 1 phân số (bài toán mở rộng), hãy đưa ra giá trị $k$ lớn nhất có thể.\r\n\r\n#### Input\r\n\r\nVào từ thiết bị vào chuẩn có khuôn dạng:\r\n- Dòng đầu ghi hai số nguyên $n, w$\r\n- Dòng thứ $i (i=1, 2, ..., n)$ trong $n$ dòng tiếp theo chứa $2$ số nguyên dương $a_i, b_i$ có giá trị không vượt quá $10^9$ lần lượt là tử số và mẫu số của phân số $i$\r\n#### Output\r\n\r\n- Ghi ra thiết bị ra chuẩn một số nguyên là giá trị $k$ lớn nhất tìm được.\r\n\r\n#### Scoring\r\n\r\n- Subtask $1$ ($25\\%$ số điểm): $n \\le 10; w = 0$;\r\n\r\n- Subtask $2$ ($25\\%$ số điểm): $n \\le 10;w = 1$;\r\n\r\n- Subtask $3$ ($25\\%$ số điểm): $n \\le 1000; w = 0$;\r\n\r\n- Subtask $4$ ($25\\%$ số điểm): $n \\le 1000;w = 0$;\r\n\r\nCó 20% số lượng test ứng với 20% số điểm có m < 10; k < n;\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4 0\r\n        5 1\r\n        1 3\r\n        3 2\r\n        1 2\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        2\r\n        ```\r\n    \r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4 1\r\n        5 1\r\n        1 3\r\n        3 2\r\n        1 2\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        3\r\n        ```","points":1700.0,"partial":true,"time_limit":2.0,"memory_limit":1048000,"short_circuit":false,"allowed_languages":[4,34,36,37,5,6,11,12,14,28,38,39,18,17,29,23,27,35,25,26,10,19,32,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}