시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 39 16 14 38.889%

문제

윤화의 직장은 여행을 온 사람들을 버스에서 안내하는 여행 가이드이다. 윤화는 어느 날 다른 날과 다름없이 N명의 사람을 버스 안에서 인솔을 하게 되었다.

그러던 도중 점심시간을 갖게 되었다. 점심시간은 한 시간인데 그 시간동안에는 N명의 사람들은 각자 자기가 가고 싶은 곳으로 갈 수 있다. 한 시간 뒤에 사람들을 버스에서 모이기로 약속을 하고 모두 흩어졌다.

그런데 일이 발생하고 말았다. 한 시간이 흘렀는데 사람들이 아무도 버스에 돌아오지 않은 것이다. 윤화는 흩어진 사람들을 모두 만나서 빨리 버스로 돌아가라고 말을 해 주고 버스로 돌아가야 한다. (단, 그 말을 들은 사람은 그 즉시 자신의 이동 방향을 바꾸어 버스를 향해 이동한다고 가정하여도 좋다.) 그런데 최대한 여행 일정이 늦어지지 않게 하기 위해서 마지막에 버스에 도착하는 사람의 시간을 최소로 하려 한다.

당신이 가지고 있는 정보는 다음과 같다. 점심시간이 끝나는 시각에 N명의 사람들의 위치의 좌표, 그리고 그 사람들의 이동 속도, 그리고 그 사람이 현재 이동하고 있는 방향이 주어진다. (모든 사람은 직선으로만 이동을 한다)

입력

첫째 줄에는 사람의 수 N(1≤N≤8)이 주어진다. 그리고 두 번째 줄에는 당신의 이동 속도가 소수로 주어진다. 그리고 세 번째 줄부터 N+2번째 줄 까지 네 개의 소수 xi,yi,vi,ai가 차례로 주어진다.  (xi, y1) (-10^6 <=xi,yi<= 10^6)는 점심시간이 끝났을 때 i번째 사람의 좌표를 의미하고, vi(1≤vi≤100)는 i번째 사람의 이동 속도를 의미한다. 그리고 ai(1≤ai≤2파이) 는 그 사람의 이동 방향을 의미한다.

출력

마지막 사람이 도착하는 시간을 소수점 첫째 자리에서 반올림하여 정수로 출력하시오. 답은 항상 106 보다 작거나 같다.

예제 입력 1

3
100.0
40.0 25.0 20.0 5.95
-185.0 195.0 6.0 2.35
30.0 -80.0 23.0 2.76

예제 출력 1

51
W3sicHJvYmxlbV9pZCI6IjE4MjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZWNcdWQ1ODlcdWFjMDBcdWM3NzRcdWI0ZGMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzcyNFx1ZDY1NFx1Yzc1OCBcdWM5YzFcdWM3YTVcdWM3NDAgXHVjNWVjXHVkNTg5XHVjNzQ0IFx1YzYyOCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDQgXHViYzg0XHVjMmE0XHVjNWQwXHVjMTFjIFx1YzU0OFx1YjBiNFx1ZDU1OFx1YjI5NCBcdWM1ZWNcdWQ1ODkgXHVhYzAwXHVjNzc0XHViNGRjXHVjNzc0XHViMmU0LiBcdWM3MjRcdWQ2NTRcdWIyOTQgXHVjNWI0XHViMjkwIFx1YjBhMCBcdWIyZTRcdWI5NzggXHViMGEwXHVhY2ZjIFx1YjJlNFx1Yjk4NFx1YzVjNlx1Yzc3NCBOXHViYTg1XHVjNzU4IFx1YzBhY1x1Yjc4Y1x1Yzc0NCBcdWJjODRcdWMyYTQgXHVjNTQ4XHVjNWQwXHVjMTFjIFx1Yzc3OFx1YzE5NFx1Yzc0NCBcdWQ1NThcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3ZWNcdWIzNTggXHViM2M0XHVjOTExIFx1YzgxMFx1YzJlY1x1YzJkY1x1YWMwNFx1Yzc0NCBcdWFjMTZcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LiBcdWM4MTBcdWMyZWNcdWMyZGNcdWFjMDRcdWM3NDAgXHVkNTVjIFx1YzJkY1x1YWMwNFx1Yzc3OFx1YjM3MCBcdWFkZjggXHVjMmRjXHVhYzA0XHViM2Q5XHVjNTQ4XHVjNWQwXHViMjk0IE5cdWJhODVcdWM3NTggXHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1YWMwMVx1Yzc5MCBcdWM3OTBcdWFlMzBcdWFjMDAgXHVhYzAwXHVhY2UwIFx1YzJmNlx1Yzc0MCBcdWFjZjNcdWM3M2NcdWI4NWMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU1YyBcdWMyZGNcdWFjMDQgXHViNGE0XHVjNWQwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0NCBcdWJjODRcdWMyYTRcdWM1ZDBcdWMxMWMgXHViYWE4XHVjNzc0XHVhZTMwXHViODVjIFx1YzU3ZFx1YzE4ZFx1Yzc0NCBcdWQ1NThcdWFjZTAgXHViYWE4XHViNDUwIFx1ZDc2OVx1YzViNFx1Yzg0Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2YwXHViMzcwIFx1Yzc3Y1x1Yzc3NCBcdWJjMWNcdWMwZGRcdWQ1NThcdWFjZTAgXHViOWQwXHVjNTU4XHViMmU0LiBcdWQ1NWMgXHVjMmRjXHVhYzA0XHVjNzc0IFx1ZDc1OFx1YjgwMFx1YjI5NFx1YjM3MCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVjNTQ0XHViYjM0XHViM2M0IFx1YmM4NFx1YzJhNFx1YzVkMCBcdWIzY2NcdWM1NDRcdWM2MjRcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNzI0XHVkNjU0XHViMjk0IFx1ZDc2OVx1YzViNFx1YzljNCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDQgXHViYWE4XHViNDUwIFx1YjljY1x1YjA5OFx1YzExYyBcdWJlNjhcdWI5YWMgXHViYzg0XHVjMmE0XHViODVjIFx1YjNjY1x1YzU0NFx1YWMwMFx1Yjc3Y1x1YWNlMCBcdWI5ZDBcdWM3NDQgXHVkNTc0IFx1YzhmY1x1YWNlMCBcdWJjODRcdWMyYTRcdWI4NWMgXHViM2NjXHVjNTQ0XHVhYzAwXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gKFx1YjJlOCwgXHVhZGY4IFx1YjlkMFx1Yzc0NCBcdWI0ZTRcdWM3NDAgXHVjMGFjXHViNzhjXHVjNzQwIFx1YWRmOCBcdWM5ODlcdWMyZGMgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Yzc3NFx1YjNkOSBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViYzE0XHVhZmI4XHVjNWI0IFx1YmM4NFx1YzJhNFx1Yjk3YyBcdWQ1YTVcdWQ1NzQgXHVjNzc0XHViM2Q5XHVkNTVjXHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1OFx1YzVlY1x1YjNjNCBcdWM4OGJcdWIyZTQuKSBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVjZDVjXHViMzAwXHVkNTVjIFx1YzVlY1x1ZDU4OSBcdWM3N2NcdWM4MTVcdWM3NzQgXHViMmE2XHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YjljOFx1YzljMFx1YjljOVx1YzVkMCBcdWJjODRcdWMyYTRcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjgyNCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJmOVx1YzJlMFx1Yzc3NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzgxNVx1YmNmNFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LiBcdWM4MTBcdWMyZWNcdWMyZGNcdWFjMDRcdWM3NzQgXHViMDVkXHViMDk4XHViMjk0IFx1YzJkY1x1YWMwMVx1YzVkMCBOXHViYTg1XHVjNzU4IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWM3NTggXHVjODhjXHVkNDVjLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc1OCBcdWM3NzRcdWIzZDkgXHVjMThkXHViM2M0LCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWQ2MDRcdWM3YWMgXHVjNzc0XHViM2Q5XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWNcdWI5Y2MgXHVjNzc0XHViM2Q5XHVjNzQ0IFx1ZDU1Y1x1YjJlNCk8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOCBOKDEmbGU7TiZsZTs4KVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZjlcdWMyZTBcdWM3NTggXHVjNzc0XHViM2Q5IFx1YzE4ZFx1YjNjNFx1YWMwMCBcdWMxOGNcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTisyXHViYzg4XHVjOWY4IFx1YzkwNCBcdWFlNGNcdWM5YzAgXHViMTI0IFx1YWMxY1x1Yzc1OCBcdWMxOGNcdWMyMTggeGkseWksdmksYWlcdWFjMDAgXHVjYzI4XHViODQwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsgKHhpLCB5MSkgKC0xMF42ICZsdDs9eGkseWkmbHQ7PSAxMF42KVx1YjI5NCBcdWM4MTBcdWMyZWNcdWMyZGNcdWFjMDRcdWM3NzQgXHViMDVkXHViMGFjXHVjNzQ0IFx1YjU0YyBpXHViYzg4XHVjOWY4IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWM4OGNcdWQ0NWNcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHVhY2UwLCB2aSgxJmxlO3ZpJmxlOzEwMClcdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjNzc0XHViM2Q5IFx1YzE4ZFx1YjNjNFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBhaSgxJmxlO2FpJmxlOzJcdWQzMGNcdWM3NzQpIFx1YjI5NCBcdWFkZjggXHVjMGFjXHViNzhjXHVjNzU4IFx1Yzc3NFx1YjNkOSBcdWJjMjlcdWQ1YTVcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWMwYWNcdWI3OGNcdWM3NzQgXHViM2M0XHVjYzI5XHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWMxOGNcdWMyMThcdWM4MTAgXHVjY2FiXHVjOWY4IFx1Yzc5MFx1YjlhY1x1YzVkMFx1YzExYyBcdWJjMThcdWM2MmNcdWI5YmNcdWQ1NThcdWM1ZWMgXHVjODE1XHVjMjE4XHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDtcdWIyZjVcdWM3NDAgXHVkNTZkXHVjMGMxIDEwPHN1cD42PFwvc3VwPiZuYnNwO1x1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE4MjciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUb3VyIEd1aWRlIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIHdvcmtpbmcgYXMgYSBndWlkZSBvbiBhIHRvdXIgYnVzIGZvciByZXRpcmVkIHBlb3BsZSwgYW5kIHRvZGF5IHlvdSBoYXZlIHRha2VuIHlvdXIgcmVndWxhciBOb3JkaWMgc2VuaW9ycyB0byBUaGUgR2F0ZSBvZiBIZWF2ZW5seSBQZWFjZS4gWW91IGxldCB0aGVtIGhhdmUgYSBsdW5jaCBicmVhayB3aGVyZSB0aGV5IGNvdWxkIGRvIHdoYXRldmVyIHRoZXkgbGlrZS4gTm93IHlvdSBoYXZlIHRvIGdldCB0aGVtIGJhY2sgdG8gdGhlIGJ1cywgYnV0IHRoZXkgYXJlIGFsbCB3YWxraW5nIGluIHJhbmRvbSBkaXJlY3Rpb25zLiBZb3UgdHJ5IHRvIGludGVyc2VjdCB0aGVtLCBhbmQgc2VuZCB0aGVtIHN0cmFpZ2h0IGJhY2sgdG8gdGhlIGJ1cy4gTWluaW1pemUgdGhlIHRpbWUgYmVmb3JlIHRoZSBsYXN0IHBlcnNvbiBpcyBpbiB0aGUgYnVzLiBZb3Ugd2lsbCBhbHdheXMgYmUgYWJsZSB0byBydW4gZmFzdGVyIHRoYW4gYW55IG9mIHRoZSB0b3VyIGd1ZXN0cywgYW5kIHRoZXkgd2FsayB3aXRoIGNvbnN0YW50IHNwZWVkLCBubyBtYXR0ZXIgd2hhdCB5b3UgdGVsbCB0aGVtLiBUaGUgc2VuaW9ycyB3YWxrIGluIHN0cmFpZ2h0IGxpbmVzLCBhbmQgdGhlIG9ubHkgd2F5IG9mIGNoYW5naW5nIHRoZWlyIGRpcmVjdGlvbiBpcyB0byBnaXZlIHRoZW0gcHJvbWlzZXMgb2YgY2FtcGhvciBjYW5keS4gQSBzZW5pb3Igd2lsbCBuZWl0aGVyIHN0b3AgYXQgbm9yIGVudGVyIHRoZSBidXMgYmVmb3JlIGdpdmVuIHN1Y2ggYSBwcm9taXNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+QSBudW1iZXIgb2YgdGVzdCBjYXNlcyBjb25zaXN0aW5nIG9mOiBBIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIDEgJmxlOyBuICZsZTsgOCwgdGhlIG51bWJlciBvZiBwZW9wbGUgb24gdGhlIHRvdXIuIEEgbGluZSB3aXRoIGFuIFx1ZmIwMm9hdGluZyBwb2ludCBudW1iZXIgMSAmbHQ7IHYgJmxlOyAxMDAsIHlvdXIgbWF4aW11bSBzcGVlZCAoeW91IHN0YXJ0IGluIHRoZSBidXMgYXQgdGhlIG9yaWdpbikuIFRoZW4gZm9sbG93IG4gbGluZXMsIGVhY2ggY29udGFpbmluZyBmb3VyIFx1ZmIwMm9hdGluZyBwb2ludCBudW1iZXJzIHg8c3ViPmk8XC9zdWI+IHk8c3ViPmk8XC9zdWI+IHY8c3ViPmk8XC9zdWI+IGE8c3ViPmk8XC9zdWI+LCB0aGUgc3RhcnRpbmcgY29vcmRpbmF0ZXMgKCZtaW51czsxMDxzdXA+NjxcL3N1cD4gJmxlOyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+NjxcL3N1cD4pLCBzcGVlZCAoMSAmbGU7IHY8c3ViPmk8XC9zdWI+ICZsdDsgMTAwKSBhbmQgZGlyZWN0aW9uICgwICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmx0OyAyJnBpOykgb2YgZWFjaCBvZiB0aGUgdG91ciBndWVzdHMuIFRoZSBpbnB1dCBpcyB0ZXJtaW5hdGVkIGJ5IGEgY2FzZSB3aXRoIG4gPSAwLCB3aGljaCBzaG91bGQgbm90IGJlIHByb2Nlc3NlZC4gQWxsIFx1ZmIwMm9hdGluZyBwb2ludCBudW1iZXJzIGluIHRoZSBpbnB1dCB3aWxsIGJlIHdyaXR0ZW4gaW4gc3RhbmRhcmQgZGVjaW1hbCBub3RhdGlvbiwgYW5kIGhhdmUgbm8gbW9yZSB0aGFuIDEwIGRpZ2l0cy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IGEgbGluZSB3aXRoIHRoZSB0aW1lIGl0IHRha2VzIGJlZm9yZSBldmVyeWJvZHkgaXMgYmFjayBpbiB0aGUgYnVzICh0aGUgb3JpZ2luKS4gUm91bmQgdGhlIGFuc3dlciB0byB0aGUgbmVhcmVzdCBpbnRlZ2VyLiBUaGUgYW5zd2VyIHdpbGwgbmV2ZXIgYmUgbGFyZ2VyIHRoYW4gMTA8c3VwPjY8XC9zdXA+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==