문제
한국과학영재학교 기숙사에는 기숙사 입구와 2ドルN + 1$개의 방이 일직선으로 배치되어 있다. 왼쪽에서 $i$번째 방이 $i$번 방이고, 기숙사 입구는 1ドル$번 방 왼쪽에 있다. 입구와 $i$번 방 사이의 거리는 $x_i$미터이다. 그중에서, $N+1$번 방은 택배물 보관실로 사용되고 있다.
예성이는 벌점이 너무 많이 쌓여서 택배물 보관실의 택배물들을 배달하게 되었다. $M$개의 택배물이 택배물 보관실에 보관되어 있고, $j$번째 택배물은 $p_j$번 방으로 배달되어야 하며 무게는 $w_j$이다. 예성이의 목표는 택배물 보관실에서 출발해 모든 택배물을 배달한 후 다시 택배물 보관실로 돌아오는 것이다. 예성이가 택배물 보관실에서 택배물을 꺼내거나 택배물을 목적지에 놓을 때는 시간이 걸리지 않는다.
너무나도 강력한 예성이는 한 번에 여러 개의 택배물을 제한 없이 들 수 있지만, 처음에 모든 택배물을 가지고 출발할 필요는 없고, 일부는 보관실에 도중에 다시 들러서 꺼내올 수도 있다. 또 택배물을 배달하는 순서는 자유롭게 정할 수 있지만, 배달되어야 하는 목적지 이외의 장소에 잠시 놓아둘 수는 없다. 예성이가 택배물을 들고 있지 않을 때의 이동 속도는 초속 1ドル$미터인데, 현재 가지고 있는 택배물 무게의 총합이 $W$일 때는 이동 속도가 초속 $\cfrac{1}{1 + W}$미터로 감소한다.
예성이는 P=NP 문제를 증명하느라 시간이 없으므로, 목표를 달성하기 위해 최소 몇 초가 걸리는지 구해주자.
출력
문제의 정답을 출력한다. 주어진 조건 하에서 정답은 정수임이 보장된다.
제한
- 1ドル \leq N, M, w_j\leq 10^5$
- 1ドル \leq x_1 < x_2 < \cdots < x_{2N+1} \leq 3 \times 10^5$
- 1ドル \leq p_j \leq 2N+1$
W3sicHJvYmxlbV9pZCI6IjMxOTg5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhZTMwXHVjMjE5XHVjMGFjIFx1ZDBkZFx1YmMzMFx1YmIzYyBcdWJjMzBcdWIyZWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU1Y1x1YWQ2ZFx1YWNmY1x1ZDU1OVx1YzYwMVx1YzdhY1x1ZDU1OVx1YWQ1MCBcdWFlMzBcdWMyMTlcdWMwYWNcdWM1ZDBcdWIyOTQgXHVhZTMwXHVjMjE5XHVjMGFjIFx1Yzc4NVx1YWQ2Y1x1YzY0MCAkMk4gKyAxJFx1YWMxY1x1Yzc1OCBcdWJjMjlcdWM3NzQgXHVjNzdjXHVjOWMxXHVjMTIwXHVjNzNjXHViODVjIFx1YmMzMFx1Y2U1OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyAkaSRcdWJjODhcdWM5ZjggXHViYzI5XHVjNzc0ICRpJFx1YmM4OCBcdWJjMjlcdWM3NzRcdWFjZTAsIFx1YWUzMFx1YzIxOVx1YzBhYyBcdWM3ODVcdWFkNmNcdWIyOTQgJDEkXHViYzg4IFx1YmMyOSBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWM3ODVcdWFkNmNcdWM2NDAgJGkkXHViYzg4IFx1YmMyOSBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0ICR4X2kkXHViYmY4XHVkMTMwXHVjNzc0XHViMmU0LiBcdWFkZjhcdWM5MTFcdWM1ZDBcdWMxMWMsICROKzEkXHViYzg4IFx1YmMyOVx1Yzc0MCBcdWQwZGRcdWJjMzBcdWJiM2MgXHViY2Y0XHVhZDAwXHVjMmU0XHViODVjIFx1YzBhY1x1YzZhOVx1YjQxOFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1YzEzMVx1Yzc3NFx1YjI5NCBcdWJjOGNcdWM4MTBcdWM3NzQgXHViMTA4XHViYjM0IFx1YjljZVx1Yzc3NCBcdWMzMTNcdWM1ZWNcdWMxMWMgXHVkMGRkXHViYzMwXHViYjNjIFx1YmNmNFx1YWQwMFx1YzJlNFx1Yzc1OCBcdWQwZGRcdWJjMzBcdWJiM2NcdWI0ZTRcdWM3NDQgXHViYzMwXHViMmVjXHVkNTU4XHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC4gJE0kXHVhYzFjXHVjNzU4IFx1ZDBkZFx1YmMzMFx1YmIzY1x1Yzc3NCBcdWQwZGRcdWJjMzBcdWJiM2MgXHViY2Y0XHVhZDAwXHVjMmU0XHVjNWQwIFx1YmNmNFx1YWQwMFx1YjQxOFx1YzViNCBcdWM3ODhcdWFjZTAsICRqJFx1YmM4OFx1YzlmOCBcdWQwZGRcdWJjMzBcdWJiM2NcdWM3NDAgJHBfaiRcdWJjODggXHViYzI5XHVjNzNjXHViODVjIFx1YmMzMFx1YjJlY1x1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NThcdWJhNzAgXHViYjM0XHVhYzhjXHViMjk0ICR3X2okXHVjNzc0XHViMmU0LiBcdWM2MDhcdWMxMzFcdWM3NzRcdWM3NTggXHViYWE5XHVkNDVjXHViMjk0IFx1ZDBkZFx1YmMzMFx1YmIzYyBcdWJjZjRcdWFkMDBcdWMyZTRcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTc0IFx1YmFhOFx1YjRlMCBcdWQwZGRcdWJjMzBcdWJiM2NcdWM3NDQgXHViYzMwXHViMmVjXHVkNTVjIFx1ZDZjNCBcdWIyZTRcdWMyZGMgXHVkMGRkXHViYzMwXHViYjNjIFx1YmNmNFx1YWQwMFx1YzJlNFx1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM2MDhcdWMxMzFcdWM3NzRcdWFjMDAgXHVkMGRkXHViYzMwXHViYjNjIFx1YmNmNFx1YWQwMFx1YzJlNFx1YzVkMFx1YzExYyBcdWQwZGRcdWJjMzBcdWJiM2NcdWM3NDQgXHVhZWJjXHViMGI0XHVhYzcwXHViMDk4IFx1ZDBkZFx1YmMzMFx1YmIzY1x1Yzc0NCBcdWJhYTlcdWM4MDFcdWM5YzBcdWM1ZDAgXHViMTkzXHVjNzQ0IFx1YjU0Y1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzc4XHViOWFjXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTA4XHViYjM0XHViMDk4XHViM2M0IFx1YWMxNVx1YjgyNVx1ZDU1YyBcdWM2MDhcdWMxMzFcdWM3NzRcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YzVkMCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDBkZFx1YmMzMFx1YmIzY1x1Yzc0NCBcdWM4MWNcdWQ1NWMgXHVjNWM2XHVjNzc0IFx1YjRlNCBcdWMyMTggXHVjNzg4XHVjOWMwXHViOWNjLCBcdWNjOThcdWM3NGNcdWM1ZDAgXHViYWE4XHViNGUwIFx1ZDBkZFx1YmMzMFx1YmIzY1x1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjZDljXHViYzFjXHVkNTYwIFx1ZDU0NFx1YzY5NFx1YjI5NCBcdWM1YzZcdWFjZTAsIFx1Yzc3Y1x1YmQ4MFx1YjI5NCBcdWJjZjRcdWFkMDBcdWMyZTRcdWM1ZDAgXHViM2M0XHVjOTExXHVjNWQwIFx1YjJlNFx1YzJkYyBcdWI0ZTRcdWI3ZWNcdWMxMWMgXHVhZWJjXHViMGI0XHVjNjJjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YjYxMCBcdWQwZGRcdWJjMzBcdWJiM2NcdWM3NDQgXHViYzMwXHViMmVjXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1YjI5NCBcdWM3OTBcdWM3MjBcdWI4NmRcdWFjOGMgXHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM5YzBcdWI5Y2MsIFx1YmMzMFx1YjJlY1x1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViYWE5XHVjODAxXHVjOWMwIFx1Yzc3NFx1YzY3OFx1Yzc1OCBcdWM3YTVcdWMxOGNcdWM1ZDAgXHVjN2EwXHVjMmRjIFx1YjE5M1x1YzU0NFx1YjQ1OCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWM2MDhcdWMxMzFcdWM3NzRcdWFjMDAgXHVkMGRkXHViYzMwXHViYjNjXHVjNzQ0IFx1YjRlNFx1YWNlMCBcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YjU0Y1x1Yzc1OCBcdWM3NzRcdWIzZDkgXHVjMThkXHViM2M0XHViMjk0IFx1Y2QwOFx1YzE4ZCAkMSRcdWJiZjhcdWQxMzBcdWM3NzhcdWIzNzAsIFx1ZDYwNFx1YzdhYyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1ZDBkZFx1YmMzMFx1YmIzYyBcdWJiMzRcdWFjOGNcdWM3NTggXHVjZDFkXHVkNTY5XHVjNzc0ICRXJFx1Yzc3YyBcdWI1NGNcdWIyOTQgXHVjNzc0XHViM2Q5IFx1YzE4ZFx1YjNjNFx1YWMwMCBcdWNkMDhcdWMxOGQgJFxcY2ZyYWN7MX17MSArIFd9JFx1YmJmOFx1ZDEzMFx1Yjg1YyBcdWFjMTBcdWMxOGNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1YzEzMVx1Yzc3NFx1YjI5NCBQPU5QIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWM5OWRcdWJhODVcdWQ1NThcdWIyOTBcdWI3N2MgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzVjNlx1YzczY1x1YmJjMFx1Yjg1YywgXHViYWE5XHVkNDVjXHViOTdjIFx1YjJlY1x1YzEzMVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWNkMDhcdWFjMDAgXHVhYzc4XHViOWFjXHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU3NFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggJE4sIE0kXHVjNzc0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgJDJOICsgMSRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICR4XzEsIHhfMiwgXFxjZG90cywgeF97Mk4gKzF9JFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzOCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICRNJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVkMGRkXHViYzMwXHViYjNjXHViNGU0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWRmOCBcdWM5MTEgJGokXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4ICRwX2okXHVjNjQwICR3X2okXHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWJiMzhcdWM4MWNcdWM3NTggXHVjODE1XHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjOGZjXHVjNWI0XHVjOWM0IFx1Yzg3MFx1YWM3NCBcdWQ1NThcdWM1ZDBcdWMxMWMgXHVjODE1XHViMmY1XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc4NFx1Yzc3NCBcdWJjZjRcdWM3YTVcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQxIFxcbGVxIE4sIE0sIHdfalxcbGVxIDEwXjUkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGVxIHhfMSAmbHQ7IHhfMiAmbHQ7IFxcY2RvdHMgJmx0OyB4X3syTisxfSBcXGxlcSAzIFxcdGltZXMgMTBeNSQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZXEgcF9qIFxcbGVxIDJOKzEkPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIzMTk4OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRlbGl2ZXJpbmcgUGFyY2VscyBpbiB0aGUgRG9ybWl0b3J5IiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgS29yZWEgU2NpZW5jZSBBY2FkZW15IGRvcm1pdG9yeSwgdGhlcmUmIzM5O3MgYW4gZW50cmFuY2UgYW5kICQyTiArIDEkIHJvb21zIGFycmFuZ2VkIGluIGEgc3RyYWlnaHQgbGluZS4gVGhlIHJvb21zIGFyZSBudW1iZXJlZCBmcm9tIGxlZnQgdG8gcmlnaHQsIHdpdGggdGhlIGVudHJhbmNlIGxvY2F0ZWQgdG8gdGhlIGxlZnQgb2Ygcm9vbSAkMSQuIFRoZSBkaXN0YW5jZSBiZXR3ZWVuIHRoZSBlbnRyYW5jZSBhbmQgcm9vbSAkaSQgaXMgJHhfaSQgbWV0ZXJzLiBBbW9uZyB0aGVzZSByb29tcywgcm9vbSAkTisxJCBpcyBiZWluZyB1c2VkIGFzIHBhcmNlbCBzdG9yYWdlLjxcL3A+XHJcblxyXG48cD5EdWUgdG8gYWNjdW11bGF0aW5nIG1hbnkgZGVtZXJpdCBwb2ludHMsIFllc2VvbmcgaGFzIGJlZW4gYXNzaWduZWQgdG8gZGVsaXZlciBwYXJjZWxzIGZyb20gdGhlIHN0b3JhZ2UuIFRoZXJlIGFyZSAkTSQgcGFyY2VscyBzdG9yZWQgaW4gdGhlIHN0b3JhZ2UsIGFuZCB0aGUgJGokLXRoIHBhcmNlbCBtdXN0IGJlIGRlbGl2ZXJlZCB0byByb29tICRwX2okIGFuZCB3ZWlnaHMgJHdfaiQuIFllc2VvbmcmIzM5O3Mgb2JqZWN0aXZlIGlzIHRvIGJlZ2luIGF0IHRoZSBzdG9yYWdlIHJvb20sIGRlbGl2ZXIgYWxsIHRoZSBwYXJjZWxzLCBhbmQgdGhlbiByZXR1cm4gdG8gdGhlIHN0b3JhZ2Ugcm9vbS4gSGUgY2FuIHBpY2sgdXAgYSBwYXJjZWwgZnJvbSB0aGUgc3RvcmFnZSByb29tIG9yIHB1dCBpdCBhdCBpdHMgZGVsaXZlcnkgZGVzdGluYXRpb24gd2l0aG91dCBzcGVuZGluZyBhbnkgdGltZS48XC9wPlxyXG5cclxuPHA+WWVzZW9uZyBpcyBzbyBzdHJvbmcgdGhhdCBoZSBjYW4gY2FycnkgYW55IG51bWJlciBvZiBwYXJjZWxzIGF0IG9uY2UsIGJ1dCBpdCBpcyBub3QgbmVjZXNzYXJ5IHRvIGNhcnJ5IGFsbCB0aGUgcGFyY2VscyBhdCB0aGUgc3RhcnQ7IGhlIGNhbiBtYWtlIG11bHRpcGxlIHRyaXBzIHRvIHRoZSBzdG9yYWdlIHJvb20gdG8gcGljayB1cCBhZGRpdGlvbmFsIHBhcmNlbHMgYXMgbmVlZGVkLiBBbHNvLCBwYXJjZWxzIGNhbiBiZSBkZWxpdmVyZWQgaW4gYW55IG9yZGVyLCBidXQgdGhleSBjYW5ub3QgYmUgdGVtcG9yYXJpbHkgbGVmdCBhdCBwbGFjZXMgb3RoZXIgdGhhbiB0aGVpciBkZWxpdmVyeSBkZXN0aW5hdGlvbi4gWWVzZW9uZyYjMzk7cyB3YWxraW5nIHNwZWVkIGlzIGludmVyc2VseSBwcm9wb3J0aW9uYWwgdG8gdGhlIHRvdGFsIHdlaWdodCBvZiB0aGUgcGFyY2VscyBoZSBpcyBjYXJyeWluZy4gV2l0aCBubyBwYXJjZWxzLCBoaXMgc3BlZWQgaXMgJDEkIG1ldGVyIHBlciBzZWNvbmQsIGFuZCBpdCBkZWNyZWFzZXMgdG8gJFxcY2ZyYWN7MX17MSArIFd9JCBtZXRlcnMgcGVyIHNlY29uZCB3aGVuIGNhcnJ5aW5nIGEgdG90YWwgd2VpZ2h0IG9mICRXJC48XC9wPlxyXG5cclxuPHA+U2luY2UgWWVzZW9uZyBoYXMgbm8gdGltZSB0byBzcGFyZSwgYXMgaGUgaXMgYnVzeSBwcm92aW5nIHRoZSBQPU5QIHByb2JsZW0sIGxldCYjMzk7cyBoZWxwIGhpbSBob3cgbWFueSBzZWNvbmRzIGFyZSByZXF1aXJlZCB0byBhY2hpZXZlIGhpcyBvYmplY3RpdmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgJE4sIE0kIHNlcGFyYXRlZCBieSBhIHNwYWNlLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgJDJOICsgMSQgaW50ZWdlcnMgJHhfMSwgeF8yLCBcXGNkb3RzLCB4X3syTiArMX0kIHNlcGFyYXRlZCBieSBzcGFjZXMuPFwvcD5cclxuXHJcbjxwPkZyb20gdGhlIHRoaXJkIGxpbmUgb253YXJkcywgaW5mb3JtYXRpb24gYWJvdXQgdGhlIHBhcmNlbHMgaXMgZ2l2ZW4sIGFuZCBvbiB0aGUgJGokLXRoIGxpbmUsIHR3byBpbnRlZ2VycyAkcF9qJCBhbmQgJHdfaiQgYXJlIGdpdmVuIHNlcGFyYXRlZCBieSBhIHNwYWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBhbnN3ZXIgdG8gdGhlIHByb2JsZW0uIFVuZGVyIHRoZSBnaXZlbiBjb25zdHJhaW50cywgaXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZSBhbnN3ZXIgd2lsbCBiZSBhbiBpbnRlZ2VyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDEgXFxsZXEgTiwgTSwmbmJzcDt3X2pcXGxlcSZuYnNwOzEwXjUkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGVxIHhfMSZuYnNwOyZsdDsmbmJzcDt4XzIgJmx0OyBcXGNkb3RzICZsdDsgeF97Mk4rMX0gXFxsZXEgMyZuYnNwO1xcdGltZXMgMTBeNSQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZXEgcF9qIFxcbGVxIDJOKzEkPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=