Một đoạn đường AB có độ dài 𝑙. Có 𝑛 người xuất phát từ điểm A và đi đến điểm B. Người thứ 𝑖 xuất phát vào thời điểm 𝑡𝑖 và đi với vận tốc 𝑣𝑖. Giả sử rằng không có 2 người nào cùng xuất phát tại cùng một thời điểm và cũng không có hai người nào đến đích cùng một thời điểm.
Người thứ 𝑖 và người thứ 𝑗 sẽ gặp nhau trên đường và sẽ kết bạn với nhau, cụ thể người thứ 𝑖 và người thứ 𝑗 sẽ kết bạn với nhau nếu 𝑡𝑖<𝑡𝑗 và 𝑙/𝑣𝑖+𝑡𝑖>𝑙/𝑣𝑗+𝑡𝑗.
Yêu cầu: Tìm một nhóm bạn lớn nhất mà hai người trong nhóm đều là bạn của nhau.
Input
- Dòng đầu gồm 2 số 𝑙,𝑛 (𝑙≤10^9;𝑛≤10^9)
- 𝑛 dòng tiếp theo, mỗi dòng mô tả thông tin của người thứ 𝑖 gồm 2 số 𝑡𝑖,𝑣𝑖.
Output
- Gồm một số là số bạn trong nhóm tìm được.