시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 61 18 8 19.512%

문제

재현이는 얼마 전 게임을 만들었다. 게임의 이름은 "유재민"이고, 게임의 주인공은 유재민이다.

유재민은 (0, 0)에서 레이저 빔을 발사하는 역할을 한다. 게임의 목표는, 유재민을 잘 조종해서 좌표평면 상에 있는 선분을 최대한 많이 맞추는 것이다. 유재민은 최대 K번 레이저 빔을 발사할 수 있으며, 레이저 빔이 선분의 끝점을 지나도, 맞췄다는 판정이 난다.

애석하게도, 재현이는 게임을 만들 때 몇가지 처리를 하지 못했고, 결국 한번 맞췄던 선분을 다시 맞췄을 경우 게임 프로그램이 크래시 되는 버그를 발견했다. 처음에는 당황했지만, 그래도 이런 게임도 나름 재미있을 것 같아서, 재현이는 이 게임을 최적으로 플레이 하려고 한다. 재현이를 도와서, 현재의 제약 조건 상황에서 맞출 수 있는 선분의 최대 개수를 구하자.

입력

첫번째 줄에 k, n이 주어진다. (1 ≤ k ≤ 100, 1 ≤ n ≤ 500 000)

이후 n개의 줄에 선분이 x1, y1, x2, y2 (1 ≤ x1, y1, x2, y2 ≤ 1 000 000)의 형태로 주어진다. (x1, y1)과 (x2, y2)를 잇는다는 뜻이다.

출력

한번 맞췄던 선분을 다시 맞추지 않는다는 조건 하에, 최대 K개의 레이저 빔을 쏘아서, 맞출 수 있는 최대 개수의 선분을 출력하라.

예제 입력 1

3 6
1 2 2 4
3 1 5 1
3 2 2 3
3 3 3 4
2 2 2 2
6 1 3 5

예제 출력 1

5

힌트

W3sicHJvYmxlbV9pZCI6IjEwMDA3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViODA4XHVjNzc0XHVjODAwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgXHVjNWJjXHViOWM4IFx1YzgwNCBcdWFjOGNcdWM3ODRcdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LiBcdWFjOGNcdWM3ODRcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQwICZxdW90O1x1YzcyMFx1YzdhY1x1YmJmYyZxdW90O1x1Yzc3NFx1YWNlMCwgXHVhYzhjXHVjNzg0XHVjNzU4IFx1YzhmY1x1Yzc3OFx1YWNmNVx1Yzc0MCBcdWM3MjBcdWM3YWNcdWJiZmNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcyMFx1YzdhY1x1YmJmY1x1Yzc0MCAoMCwgMClcdWM1ZDBcdWMxMWMgXHViODA4XHVjNzc0XHVjODAwIFx1YmU1NFx1Yzc0NCBcdWJjMWNcdWMwYWNcdWQ1NThcdWIyOTQgXHVjNWVkXHVkNTYwXHVjNzQ0IFx1ZDU1Y1x1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzU4IFx1YmFhOVx1ZDQ1Y1x1YjI5NCwgXHVjNzIwXHVjN2FjXHViYmZjXHVjNzQ0IFx1Yzc5OCBcdWM4NzBcdWM4ODVcdWQ1NzRcdWMxMWMgXHVjODhjXHVkNDVjXHVkM2M5XHViYTc0IFx1YzBjMVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NzQgXHViOWRlXHVjZDk0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNzIwXHVjN2FjXHViYmZjXHVjNzQwIFx1Y2Q1Y1x1YjMwMCBLXHViYzg4IFx1YjgwOFx1Yzc3NFx1YzgwMCBcdWJlNTRcdWM3NDQgXHViYzFjXHVjMGFjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YjgwOFx1Yzc3NFx1YzgwMCBcdWJlNTRcdWM3NzQgXHVjMTIwXHViZDg0XHVjNzU4IFx1YjA1ZFx1YzgxMFx1Yzc0NCBcdWM5YzBcdWIwOThcdWIzYzQsIFx1YjlkZVx1Y2RjNFx1YjJlNFx1YjI5NCBcdWQzMTBcdWM4MTVcdWM3NzQgXHViMDljXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NjBcdWMxMWRcdWQ1NThcdWFjOGNcdWIzYzQsIFx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHViOWNjXHViNGU0IFx1YjU0YyBcdWJhODdcdWFjMDBcdWM5YzAgXHVjYzk4XHViOWFjXHViOTdjIFx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1ODhcdWFjZTAsIFx1YWNiMFx1YWQ2ZCBcdWQ1NWNcdWJjODggXHViOWRlXHVjZGM0XHViMzU4IFx1YzEyMFx1YmQ4NFx1Yzc0NCBcdWIyZTRcdWMyZGMgXHViOWRlXHVjZGM0XHVjNzQ0IFx1YWNiZFx1YzZiMCBcdWFjOGNcdWM3ODQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1ZDA2Y1x1Yjc5OFx1YzJkYyBcdWI0MThcdWIyOTQgXHViYzg0XHVhZGY4XHViOTdjIFx1YmMxY1x1YWNhY1x1ZDU4OFx1YjJlNC4gXHVjYzk4XHVjNzRjXHVjNWQwXHViMjk0IFx1YjJmOVx1ZDY2OVx1ZDU4OFx1YzljMFx1YjljYywgXHVhZGY4XHViNzk4XHViM2M0IFx1Yzc3NFx1YjdmMCBcdWFjOGNcdWM3ODRcdWIzYzQgXHViMDk4XHViOTg0IFx1YzdhY1x1YmJmOFx1Yzc4OFx1Yzc0NCBcdWFjODMgXHVhYzE5XHVjNTQ0XHVjMTFjLCBcdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWNkNWNcdWM4MDFcdWM3M2NcdWI4NWMgXHVkNTBjXHViODA4XHVjNzc0IFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzdhY1x1ZDYwNFx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDBcdWMxMWMsIFx1ZDYwNFx1YzdhY1x1Yzc1OCBcdWM4MWNcdWM1N2QgXHVjODcwXHVhYzc0IFx1YzBjMVx1ZDY2OVx1YzVkMFx1YzExYyBcdWI5ZGVcdWNkOWMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIGssIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOygxICZsZTsgayAmbGU7IDEwMCwgMSAmbGU7IG4gJmxlOyA1MDAgMDAwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjMTIwXHViZDg0XHVjNzc0IHgxLCB5MSwgeDIsIHkyICgxICZsZTsgeDEsIHkxLCB4MiwgeTIgJmxlOyAxIDAwMCAwMDApXHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICh4MSwgeTEpXHVhY2ZjICh4MiwgeTIpXHViOTdjIFx1Yzc4N1x1YjI5NFx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNTVjXHViYzg4IFx1YjlkZVx1Y2RjNFx1YjM1OCBcdWMxMjBcdWJkODRcdWM3NDQgXHViMmU0XHVjMmRjIFx1YjlkZVx1Y2Q5NFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWIyOTQgXHVjODcwXHVhYzc0IFx1ZDU1OFx1YzVkMCwgXHVjZDVjXHViMzAwIEtcdWFjMWNcdWM3NTggXHViODA4XHVjNzc0XHVjODAwIFx1YmU1NFx1Yzc0NCBcdWMzZDhcdWM1NDRcdWMxMWMsIFx1YjlkZVx1Y2Q5YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWM3NTggXHVjMTIwXHViZDg0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTAwMDdcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjE2cHg7IHdpZHRoOjIxNXB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDAwNyIsInByb2JsZW1fbGFuZyI6IjMiLCJ0aXRsZSI6Ikxhc2VyIiwiZGVzY3JpcHRpb24iOiI8cD5LYXBpdGFuIEJhanRhemFyIHBvbHVqZSBuYSBvZGNpbmtvd2NlIG5hIHBsYW5lY2llIFR1bXVsdW0gVkkuIEplZ28gc3RhdGVrIHN0b2kgdyBtaWVqc2N1IGxcdTAxMDVkb3dhbmlhIChrdCZvYWN1dGU7cmUgYlx1MDExOWR6aWVteSB1d2FcdTAxN2NhXHUwMTA3IHphIHBvY3pcdTAxMDV0ZWsgdWtcdTAxNDJhZHUgd3NwJm9hY3V0ZTtcdTAxNDJyelx1MDExOWRueWNoKSBpIHd5cG9zYVx1MDE3Y29ueSBqZXN0IHcgbGFzZXIgb2dcdTAxNDJ1c3phalx1MDEwNWN5LiBMYXNlcmVtIHR5bSBtb1x1MDE3Y25hIG9icmFjYVx1MDEwNywgdGFrIGFieSBwcm9taWVcdTAxNDQgbGFzZXJhIGJ5XHUwMTQyIHNraWVyb3dhbnkgcG9kIGRvd29sbnltIGtcdTAxMDV0ZW0uIFphc2lsYW5pYSBzdGF0a3Ugd3lzdGFyY3p5IG5hIGNvIG5hand5XHUwMTdjZWogJm5ic3A7c3RyemFcdTAxNDImb2FjdXRlO3csIHoga3Qmb2FjdXRlO3J5Y2gga2FcdTAxN2NkeSBtb1x1MDE3Y2UgYnlcdTAxMDcgb2RkYW55IHBvZCBkb3dvbG5pZSB3eWJyYW55bSBrXHUwMTA1dGVtLiBXIG1vbWVuY2llLCBnZHkgbGFzZXIgamVzdCB3XHUwMTQyXHUwMTA1Y3pvbnksIG5pZSBtb1x1MDE3Y25hIG5pbSBvYnJhY2FcdTAxMDcuPFwvcD5cclxuXHJcbjxwPk5hIHBsYW5lY2llIHpuYWpkdWplIHNpXHUwMTE5ICZuYnNwO29kY2lua293YyZvYWN1dGU7dyAtIGthXHUwMTdjZHkgeiBuaWNoIGplc3QgaXN0b3RcdTAxMDUgamVkbm93eW1pYXJvd1x1MDEwNSAob2RjaW5raWVtKSBvIGtvXHUwMTQ0Y2FjaCB3IHB1bmt0YWNoIG8gd3NwJm9hY3V0ZTtcdTAxNDJyelx1MDExOWRueWNoIGRvZGF0bmljaCBpIGNhXHUwMTQya293aXR5Y2guIENlbGVtIEJhanRhemFyYSBqZXN0IHRyYWZpZW5pZSBwcm9taWVuaWVtIGxhc2VyYSBqYWsgbmFqd2lcdTAxMTlrc3plaiBsaWN6Ynkgb2RjaW5rb3djJm9hY3V0ZTt3LCBwcnp5IGN6eW0gemFicm9uaW9uZSBqZXN0IHRyYWZpZW5pZSBqYWtpZWdvXHUwMTViIG9kY2lua293Y2Egd2lcdTAxMTljZWogbmlcdTAxN2MgcmF6IC0ga2FwaXRhbiBjaGNlIGplIHNwcnplZGFcdTAxMDcgeiBkb2JyeW0genlza2llbSwgYSBkbyB0ZWdvIG11c3pcdTAxMDUgYnlcdTAxMDcgdyBuaWVuYWdhbm55bSBzdGFuaWUgZml6eWN6bnltIGkgcHN5Y2hpY3pueW0uIFByb21pZVx1MDE0NCBsYXNlcmEgcm96Y2hvZHppIHNpXHUwMTE5IHd6ZFx1MDE0MnVcdTAxN2MgcHJvc3RlaiwgYSBnZHkgdHJhZmlhIG9kY2luZWssIHByemVuaWthIHByemV6IG5pZWdvIGkgYmllZ25pZSBkYWxlai4gSmVcdTAxNWJsaSBwcm9taWVcdTAxNDQgbGFzZXJhIHByemVqZHppZSBwcnpleiBzYW0ga29uaWVjIGx1YiB3emRcdTAxNDJ1XHUwMTdjIG9kY2lua293Y2EsIHRvIHImb2FjdXRlO3duaWVcdTAxN2MgamVzdCBvbiB0cmFmaW9ueS48XC9wPlxyXG5cclxuPHA+TmFwaXN6IHByb2dyYW0sIGt0Jm9hY3V0ZTtyeSB3eXpuYWN6eSBtYWtzeW1hbG5cdTAxMDUgbGljemJcdTAxMTkgb2RjaW5rb3djJm9hY3V0ZTt3LCBrdCZvYWN1dGU7cmUgbW9cdTAxN2NuYSB0cmFmaVx1MDEwNyBwcm9taWVuaWVtIGxhc2VyYSwgemdvZG5pZSB6IHBvZGFueW1pIHBvd3lcdTAxN2NlaiB6YXNhZGFtaS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlcgcGllcndzenltIHdpZXJzenUgc3RhbmRhcmRvd2VnbyB3ZWpcdTAxNWJjaWEgem5hamR1alx1MDEwNSBzaVx1MDExOSBkd2llIGxpY3pieSBjYVx1MDE0Mmtvd2l0ZSBrIGkgbiAoMSAmbGU7IGsgJmxlOyAxMDAsIDEgJmxlOyBuICZsZTsgNTAwIDAwMCksIG9kZHppZWxvbmUgcG9qZWR5bmN6eW0gb2RzdFx1MDExOXBlbS4gVyBrb2xlam55Y2ggd2llcnN6YWNoIG9waXNhbmUgc1x1MDEwNSBvZGNpbmtvd2NlLCBwbyBqZWRueW0gdyB3aWVyc3p1LiBXIGthXHUwMTdjZHltIHogdHljaCB3aWVyc3p5IHpuYWpkdWpcdTAxMDUgc2lcdTAxMTkgcG8gY3p0ZXJ5IGRvZGF0bmllIGxpY3pieSBjYVx1MDE0Mmtvd2l0ZSB4MSwgeTEsIHgyLCB5MiAoMSAmbGU7IHgxLCB5MSwgeDIsIHkyICZsZTsgMSAwMDAgMDAwKSwgcm96ZHppZWxvbmUgcG9qZWR5bmN6eW1pIG9kc3RcdTAxMTlwYW1pLiBMaWN6YnkgdGFraWUgcmVwcmV6ZW50dWpcdTAxMDUgb2RjaW5rb3djYSBvIGtvXHUwMTQ0Y2FjaCAoeDEsIHkxKSBpICh4MiwgeTIpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlR3Jm9hY3V0ZTtqIHByb2dyYW0gcG93aW5pZW4gd3lwaXNhXHUwMTA3IHcgcGllcndzenltIChpIGplZHlueW0pIHdpZXJzenUgc3RhbmRhcmRvd2VnbyB3eWpcdTAxNWJjaWEgZG9rXHUwMTQyYWRuaWUgamVkblx1MDEwNSBsaWN6Ylx1MDExOSBjYVx1MDE0Mmtvd2l0XHUwMTA1OiBtYWtzeW1hbG5cdTAxMDUgbGljemJcdTAxMTkgb2RjaW5rb3djJm9hY3V0ZTt3LCBrdCZvYWN1dGU7cmUgbW9cdTAxN2NuYSB0cmFmaVx1MDEwNyBwcm9taWVuaWVtIGxhc2VyYSAoa2FcdTAxN2NkZWdvIGRva1x1MDE0MmFkbmllIHJheiksIHd5a29udWpcdTAxMDVjIGNvIG5hand5XHUwMTdjZWogayBzdHJ6YVx1MDE0MiZvYWN1dGU7dy48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTAwMDdcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjE2cHg7IHdpZHRoOjIxNXB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQzZjRcdWI3ODBcdWI0ZGNcdWM1YjQifV0=