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.

Bà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ể.

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ể.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu ghi hai số nguyên \(n, w\)
• 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\)

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là giá trị \(k\) lớn nhất tìm được.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 10; w = 0\);

• Subtask \(2\) (\(25\%\) số điểm): \(n \le 10;w = 1\);

• Subtask \(3\) (\(25\%\) số điểm): \(n \le 1000; w = 0\);

• Subtask \(4\) (\(25\%\) số điểm): \(n \le 1000;w = 0\);

Có 20% số lượng test ứng với 20% số điểm có m < 10; k < n;

Example

4 0
5 1
1 3
3 2
1 2

2

4 1
5 1
1 3
3 2
1 2

3