시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 69 22 11 22.917%

문제

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

유재민은 (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+XHJcblxyXG48cD5cdWM1NjBcdWMxMWRcdWQ1NThcdWFjOGNcdWIzYzQsIFx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHViOWNjXHViNGU0IFx1YjU0YyBcdWJhODcgXHVhYzAwXHVjOWMwIFx1Y2M5OFx1YjlhY1x1Yjk3YyBcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTg4XHVhY2UwLCBcdWFjYjBcdWFkNmQgXHVkNTVjXHViYzg4IFx1YjlkZVx1Y2RjNFx1YjM1OCBcdWMxMjBcdWJkODRcdWM3NDQgXHViMmU0XHVjMmRjIFx1YjlkZVx1Y2RjNFx1Yzc0NCBcdWFjYmRcdWM2YjAgXHVhYzhjXHVjNzg0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NCBcdWQwNmNcdWI3OThcdWMyZGMgXHViNDE4XHViMjk0IFx1YmM4NFx1YWRmOFx1Yjk3YyBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1Y2M5OFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWIyZjlcdWQ2NjlcdWQ1ODhcdWM5YzBcdWI5Y2MsIFx1YWRmOFx1Yjc5OFx1YjNjNCBcdWM3NzRcdWI3ZjAgXHVhYzhjXHVjNzg0XHViM2M0IFx1YjA5OFx1Yjk4NCBcdWM3YWNcdWJiZjhcdWM3ODhcdWM3NDQgXHVhYzgzIFx1YWMxOVx1YzU0NFx1YzExYywgXHVjN2FjXHVkNjA0XHVjNzc0XHViMjk0IFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjZDVjXHVjODAxXHVjNzNjXHViODVjIFx1ZDUwY1x1YjgwOFx1Yzc3NCBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3YWNcdWQ2MDRcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwXHVjMTFjLCBcdWQ2MDRcdWM3YWNcdWM3NTggXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NCBcdWMwYzFcdWQ2NjlcdWM1ZDBcdWMxMWMgXHViOWRlXHVjZDljIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgaywgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDEgJmxlOyBrICZsZTsgMTAwLCAxICZsZTsgbiAmbGU7IDUwMCAwMDApPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWMxMjBcdWJkODRcdWM3NzQgeDEsIHkxLCB4MiwgeTIgKDEgJmxlOyB4MSwgeTEsIHgyLCB5MiAmbGU7IDEgMDAwIDAwMClcdWM3NTggXHVkNjE1XHVkMGRjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKHgxLCB5MSlcdWFjZmMgKHgyLCB5MilcdWI5N2MgXHVjNzg3XHViMjk0XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ1NWNcdWJjODggXHViOWRlXHVjZGM0XHViMzU4IFx1YzEyMFx1YmQ4NFx1Yzc0NCBcdWIyZTRcdWMyZGMgXHViOWRlXHVjZDk0XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YjI5NCBcdWM4NzBcdWFjNzQgXHVkNTU4XHVjNWQwLCBcdWNkNWNcdWIzMDAgS1x1YWMxY1x1Yzc1OCBcdWI4MDhcdWM3NzRcdWM4MDAgXHViZTU0XHVjNzQ0IFx1YzNkOFx1YzU0NFx1YzExYywgXHViOWRlXHVjZDljIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWMxMjBcdWJkODRcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xMDAwN1wvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMTZweDsgd2lkdGg6MjE1cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwMDA3IiwicHJvYmxlbV9sYW5nIjoiMyIsInRpdGxlIjoiTGFzZXIiLCJkZXNjcmlwdGlvbiI6IjxwPkthcGl0YW4gQmFqdGF6YXIgcG9sdWplIG5hIG9kY2lua293Y2UgbmEgcGxhbmVjaWUgVHVtdWx1bSBWSS4gSmVnbyBzdGF0ZWsgc3RvaSB3IG1pZWpzY3UgbFx1MDEwNWRvd2FuaWEgKGt0Jm9hY3V0ZTtyZSBiXHUwMTE5ZHppZW15IHV3YVx1MDE3Y2FcdTAxMDcgemEgcG9jelx1MDEwNXRlayB1a1x1MDE0MmFkdSB3c3Amb2FjdXRlO1x1MDE0MnJ6XHUwMTE5ZG55Y2gpIGkgd3lwb3NhXHUwMTdjb255IGplc3QgdyBsYXNlciBvZ1x1MDE0MnVzemFqXHUwMTA1Y3kuIExhc2VyZW0gdHltIG1vXHUwMTdjbmEgb2JyYWNhXHUwMTA3LCB0YWsgYWJ5IHByb21pZVx1MDE0NCBsYXNlcmEgYnlcdTAxNDIgc2tpZXJvd2FueSBwb2QgZG93b2xueW0ga1x1MDEwNXRlbS4gWmFzaWxhbmlhIHN0YXRrdSB3eXN0YXJjenkgbmEgY28gbmFqd3lcdTAxN2NlaiAmbmJzcDtzdHJ6YVx1MDE0MiZvYWN1dGU7dywgeiBrdCZvYWN1dGU7cnljaCBrYVx1MDE3Y2R5IG1vXHUwMTdjZSBieVx1MDEwNyBvZGRhbnkgcG9kIGRvd29sbmllIHd5YnJhbnltIGtcdTAxMDV0ZW0uIFcgbW9tZW5jaWUsIGdkeSBsYXNlciBqZXN0IHdcdTAxNDJcdTAxMDVjem9ueSwgbmllIG1vXHUwMTdjbmEgbmltIG9icmFjYVx1MDEwNy48XC9wPlxyXG5cclxuPHA+TmEgcGxhbmVjaWUgem5hamR1amUgc2lcdTAxMTkgJm5ic3A7b2RjaW5rb3djJm9hY3V0ZTt3IC0ga2FcdTAxN2NkeSB6IG5pY2ggamVzdCBpc3RvdFx1MDEwNSBqZWRub3d5bWlhcm93XHUwMTA1IChvZGNpbmtpZW0pIG8ga29cdTAxNDRjYWNoIHcgcHVua3RhY2ggbyB3c3Amb2FjdXRlO1x1MDE0MnJ6XHUwMTE5ZG55Y2ggZG9kYXRuaWNoIGkgY2FcdTAxNDJrb3dpdHljaC4gQ2VsZW0gQmFqdGF6YXJhIGplc3QgdHJhZmllbmllIHByb21pZW5pZW0gbGFzZXJhIGphayBuYWp3aVx1MDExOWtzemVqIGxpY3pieSBvZGNpbmtvd2Mmb2FjdXRlO3csIHByenkgY3p5bSB6YWJyb25pb25lIGplc3QgdHJhZmllbmllIGpha2llZ29cdTAxNWIgb2RjaW5rb3djYSB3aVx1MDExOWNlaiBuaVx1MDE3YyByYXogLSBrYXBpdGFuIGNoY2UgamUgc3ByemVkYVx1MDEwNyB6IGRvYnJ5bSB6eXNraWVtLCBhIGRvIHRlZ28gbXVzelx1MDEwNSBieVx1MDEwNyB3IG5pZW5hZ2FubnltIHN0YW5pZSBmaXp5Y3pueW0gaSBwc3ljaGljem55bS4gUHJvbWllXHUwMTQ0IGxhc2VyYSByb3pjaG9kemkgc2lcdTAxMTkgd3pkXHUwMTQydVx1MDE3YyBwcm9zdGVqLCBhIGdkeSB0cmFmaWEgb2RjaW5laywgcHJ6ZW5pa2EgcHJ6ZXogbmllZ28gaSBiaWVnbmllIGRhbGVqLiBKZVx1MDE1YmxpIHByb21pZVx1MDE0NCBsYXNlcmEgcHJ6ZWpkemllIHByemV6IHNhbSBrb25pZWMgbHViIHd6ZFx1MDE0MnVcdTAxN2Mgb2RjaW5rb3djYSwgdG8gciZvYWN1dGU7d25pZVx1MDE3YyBqZXN0IG9uIHRyYWZpb255LjxcL3A+XHJcblxyXG48cD5OYXBpc3ogcHJvZ3JhbSwga3Qmb2FjdXRlO3J5IHd5em5hY3p5IG1ha3N5bWFsblx1MDEwNSBsaWN6Ylx1MDExOSBvZGNpbmtvd2Mmb2FjdXRlO3csIGt0Jm9hY3V0ZTtyZSBtb1x1MDE3Y25hIHRyYWZpXHUwMTA3IHByb21pZW5pZW0gbGFzZXJhLCB6Z29kbmllIHogcG9kYW55bWkgcG93eVx1MDE3Y2VqIHphc2FkYW1pLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VyBwaWVyd3N6eW0gd2llcnN6dSBzdGFuZGFyZG93ZWdvIHdlalx1MDE1YmNpYSB6bmFqZHVqXHUwMTA1IHNpXHUwMTE5IGR3aWUgbGljemJ5IGNhXHUwMTQya293aXRlIGsgaSBuICgxICZsZTsgayAmbGU7IDEwMCwgMSAmbGU7IG4gJmxlOyA1MDAgMDAwKSwgb2RkemllbG9uZSBwb2plZHluY3p5bSBvZHN0XHUwMTE5cGVtLiBXIGtvbGVqbnljaCB3aWVyc3phY2ggb3Bpc2FuZSBzXHUwMTA1IG9kY2lua293Y2UsIHBvIGplZG55bSB3IHdpZXJzenUuIFcga2FcdTAxN2NkeW0geiB0eWNoIHdpZXJzenkgem5hamR1alx1MDEwNSBzaVx1MDExOSBwbyBjenRlcnkgZG9kYXRuaWUgbGljemJ5IGNhXHUwMTQya293aXRlIHgxLCB5MSwgeDIsIHkyICgxICZsZTsgeDEsIHkxLCB4MiwgeTIgJmxlOyAxIDAwMCAwMDApLCByb3pkemllbG9uZSBwb2plZHluY3p5bWkgb2RzdFx1MDExOXBhbWkuIExpY3pieSB0YWtpZSByZXByZXplbnR1alx1MDEwNSBvZGNpbmtvd2NhIG8ga29cdTAxNDRjYWNoICh4MSwgeTEpIGkgKHgyLCB5MikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VHcmb2FjdXRlO2ogcHJvZ3JhbSBwb3dpbmllbiB3eXBpc2FcdTAxMDcgdyBwaWVyd3N6eW0gKGkgamVkeW55bSkgd2llcnN6dSBzdGFuZGFyZG93ZWdvIHd5alx1MDE1YmNpYSBkb2tcdTAxNDJhZG5pZSBqZWRuXHUwMTA1IGxpY3piXHUwMTE5IGNhXHUwMTQya293aXRcdTAxMDU6IG1ha3N5bWFsblx1MDEwNSBsaWN6Ylx1MDExOSBvZGNpbmtvd2Mmb2FjdXRlO3csIGt0Jm9hY3V0ZTtyZSBtb1x1MDE3Y25hIHRyYWZpXHUwMTA3IHByb21pZW5pZW0gbGFzZXJhIChrYVx1MDE3Y2RlZ28gZG9rXHUwMTQyYWRuaWUgcmF6KSwgd3lrb251alx1MDEwNWMgY28gbmFqd3lcdTAxN2NlaiBrIHN0cnphXHUwMTQyJm9hY3V0ZTt3LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xMDAwN1wvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMTZweDsgd2lkdGg6MjE1cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDNmNFx1Yjc4MFx1YjRkY1x1YzViNCJ9XQ==