시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 36 8 7 43.750%

문제

이 나라의 교통망은 N개의 도시로 이루어져 있으며(1~N의 정수로 번호가 매겨져 있다) N-1개의 도로가 도시들을 연결한다. 서로 다른 두 도시 간에는 특별한 경로가 존재한다.

수년간의 게으른 도로 보수로 인해 도로는 꽤 손상되었고 각각의 도로는 A와 B의 숫자를 가지고 있다. 정수 A는 현재 해당 도로를 통해서 이동할 때 걸리는 시간을 나타내며, 정수 B는 만일 모든 도로를 복구해 놓았을 경우, 이 도로를 통해서 이동할 때 걸리는 최소 시간(초 단위)을 나타낸다.

도로를 복구하는 데에 일정 금액의 비용을 투자할 것이다. 특정 도로는 투자한 비용에 비례하여 그 결과가 나타날 것이다. 각 금액(유로)은 몇몇 도로에 투자될 것이며, 도로를 따라 이동하는데 걸리는 시간은 매 순간 감소할 것이다(도로에 투자하는 비용은 정수이다). 이동 소요 시간은 가능한 최솟값인 B보다 작아질 수 없다.

일정 금액의 돈이 주어지면, 이 돈을 '도시 1'에서부터 가장 먼 도시까지 걸리는 이동 소요시간(모든 복구 작업이 끝난 후)이 최소한이 되는 방법으로 도로에 분배하고 싶다.

입력

첫째 줄에 도시의 개수 N과 총 금액 K(유로)가 주어진다. (2 ≤ N ≤ 100 000, 0 ≤ K ≤ 1 000 000)

둘째 줄부터 N-1개의 줄에 4개의 정수 X, Y, A, B가 주어진다. 이는 도시X와 도시Y 사이에 도로가 있으며, 현재 소요시간 A과 문제에서 언급한 최소 시간 B를 나타낸다. (0 ≤ B ≤ A ≤ 10 000)

출력

최소 시간을 출력한다.

예제 입력 1

3 200
1 2 200 100
2 3 450 250

예제 출력 1

450
W3sicHJvYmxlbV9pZCI6IjMxODAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMTRcdWIwOThcdWIwOTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc3NCBcdWIwOThcdWI3N2NcdWM3NTggXHVhZDUwXHVkMWI1XHViOWRkXHVjNzQwIE5cdWFjMWNcdWM3NTggXHViM2M0XHVjMmRjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAoMX5OXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyZuYnNwO1x1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0KSBOLTFcdWFjMWNcdWM3NTggXHViM2M0XHViODVjXHVhYzAwIFx1YjNjNFx1YzJkY1x1YjRlNFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YjNjNFx1YzJkYyBcdWFjMDRcdWM1ZDBcdWIyOTQgXHVkMmI5XHViY2M0XHVkNTVjIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzIxOFx1YjE0NFx1YWMwNFx1Yzc1OCBcdWFjOGNcdWM3M2NcdWI5NzggXHViM2M0XHViODVjIFx1YmNmNFx1YzIxOFx1Yjg1YyBcdWM3NzhcdWQ1NzQgXHViM2M0XHViODVjXHViMjk0IFx1YWY2NCBcdWMxOTBcdWMwYzFcdWI0MThcdWM1YzhcdWFjZTAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YjI5NCBBXHVjNjQwIEJcdWM3NTggXHVjMjJiXHVjNzkwXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzgxNVx1YzIxOCBBXHViMjk0IFx1ZDYwNFx1YzdhYyBcdWQ1NzRcdWIyZjkgXHViM2M0XHViODVjXHViOTdjIFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCBcdWM4MTVcdWMyMTggQlx1YjI5NCBcdWI5Y2NcdWM3N2MgXHViYWE4XHViNGUwIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWJjZjVcdWFkNmNcdWQ1NzQgXHViMTkzXHVjNTU4XHVjNzQ0IFx1YWNiZFx1YzZiMCwgXHVjNzc0IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWQxYjVcdWQ1NzRcdWMxMWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YjU0YyBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNChcdWNkMDggXHViMmU4XHVjNzA0KVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWJjZjVcdWFkNmNcdWQ1NThcdWIyOTQgXHViMzcwXHVjNWQwIFx1Yzc3Y1x1YzgxNSBcdWFlMDhcdWM1NjFcdWM3NTggXHViZTQ0XHVjNmE5XHVjNzQ0IFx1ZDIyY1x1Yzc5MFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1ZDJiOVx1YzgxNSBcdWIzYzRcdWI4NWNcdWIyOTQgXHVkMjJjXHVjNzkwXHVkNTVjIFx1YmU0NFx1YzZhOVx1YzVkMCBcdWJlNDRcdWI4NDBcdWQ1NThcdWM1ZWMgXHVhZGY4IFx1YWNiMFx1YWNmY1x1YWMwMCBcdWIwOThcdWQwYzBcdWIwYTAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFjMDEgXHVhZTA4XHVjNTYxKFx1YzcyMFx1Yjg1YylcdWM3NDAgXHViYTg3XHViYTg3IFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWQyMmNcdWM3OTBcdWI0MjAgXHVhYzgzXHVjNzc0XHViYTcwLCBcdWIzYzRcdWI4NWNcdWI5N2MgXHViNTMwXHViNzdjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIFx1YjllNCBcdWMyMWNcdWFjMDQgXHVhYzEwXHVjMThjXHVkNTYwIFx1YWM4M1x1Yzc3NFx1YjJlNChcdWIzYzRcdWI4NWNcdWM1ZDAgXHVkMjJjXHVjNzkwXHVkNTU4XHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQpLiBcdWM3NzRcdWIzZDkgXHVjMThjXHVjNjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzc4IEJcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNTQ0XHVjOWM4IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3Y1x1YzgxNSBcdWFlMDhcdWM1NjFcdWM3NTggXHViM2M4XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCwgXHVjNzc0IFx1YjNjOFx1Yzc0NCAmIzM5O1x1YjNjNFx1YzJkYyAxJiMzOTtcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVhYzAwXHVjN2E1IFx1YmEzYyBcdWIzYzRcdWMyZGNcdWFlNGNcdWM5YzAgXHVhYzc4XHViOWFjXHViMjk0IFx1Yzc3NFx1YjNkOSBcdWMxOGNcdWM2OTRcdWMyZGNcdWFjMDQoXHViYWE4XHViNGUwIFx1YmNmNVx1YWQ2YyBcdWM3OTFcdWM1YzVcdWM3NzQgXHViMDVkXHViMDljIFx1ZDZjNClcdWM3NzQgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzc0IFx1YjQxOFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHViM2M0XHViODVjXHVjNWQwIFx1YmQ4NFx1YmMzMFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjgmbmJzcDtcdWM5MDRcdWM1ZDAgXHViM2M0XHVjMmRjXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVhY2ZjIFx1Y2QxZCBcdWFlMDhcdWM1NjEgSyhcdWM3MjBcdWI4NWMpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMiAmbGU7IE4gJmxlOyAxMDAgMDAwLCAwICZsZTsgSyAmbGU7IDEgMDAwIDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOLTFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIDRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IFgsIFksIEEsIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQmbmJzcDtcdWIzYzRcdWMyZGNYXHVjNjQwIFx1YjNjNFx1YzJkY1kgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWM3M2NcdWJhNzAsJm5ic3A7XHVkNjA0XHVjN2FjIFx1YzE4Y1x1YzY5NFx1YzJkY1x1YWMwNCBBXHVhY2ZjJm5ic3A7XHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzViOFx1YWUwOVx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0IEJcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiAoMCAmbGU7IEIgJmxlOyBBICZsZTsgMTAmbmJzcDswMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE4MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6ImJhbmFuYSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHRyYWZmaWMgbmV0d29yayBpbiBhIGNvdW50cnkgY29uc2lzdHMgb2YgTiBjaXRpZXMgKGxhYmVsZWQgd2l0aCBpbnRlZ2VycyAxIHRvIE4pIGFuZCBOLTEgcm9hZHMgY29ubmVjdGluZyB0aGUgY2l0aWVzLiBUaGVyZSBpcyBhIHVuaXF1ZSBwYXRoIGJldHdlZW4gZWFjaCBwYWlyIG9mIGRpZmZlcmVudCBjaXRpZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkJlY2F1c2Ugb2YgdGhlIG1hbnkgeWVhcnMgb2YgbGF6eSBtYWludGVuYW5jZSB0aGUgcm9hZHMgYXJlIHByZXR0eSBkYW1hZ2VkIGFuZCBmb3IgZWFjaCByb2FkIHR3byBudW1iZXJzIEEgYW5kIEIgYXJlIGtub3duICZuZGFzaDsgdGhlIGludGVnZXIgQSByZXByZXNlbnRzIHRoZSBjdXJyZW50IHRpbWUgKGluIHNlY29uZHMpIG5lZWRlZCB0byB0cmF2ZWwgYWxvbmcgdGhlIHJvYWQsIGFuZCB0aGUgaW50ZWdlciBCIHJlcHJlc2VudHMgdGhlIHNtYWxsZXN0IHBvc3NpYmxlIHRpbWUgKGluIHNlY29uZHMpIG5lZWRlZCB0byB0cmF2ZWwgYWxvbmcgdGhpcyByb2FkIGlmIHdlIHJlcGFpciBhbGwgdGhlIGRhbWFnZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2Ugd2FudCB0byBpbnZlc3QgYSBjZXJ0YWluIGFtb3VudCBvZiBtb25leSBpbnRvIHJvYWQgcmVwYWlyLiBGb3IgYSBwYXJ0aWN1bGFyIHJvYWQsIHRoZSByZXN1bHQgd2lsbCBiZSBwcm9wb3J0aW9uYWwgdG8gdGhlIGFtb3VudCBvZiBpbnZlc3RlZCBtb25leS4gRm9yIGVhY2ggZXVybyBpbnZlc3RlZCBpbiBzb21lIHJvYWQsIHRoZSB0aW1lIG5lZWRlZCB0byB0cmF2ZWwgYWxvbmcgdGhhdCByb2FkIHdpbGwgYmUgcmVkdWNlZCBieSBvbmUgc2Vjb25kICh0aGUgYW1vdW50IG9mIG1vbmV5IGludmVzdGVkIGluIHNvbWUgcm9hZCBoYXMgdG8gYmUgYW4gaW50ZWdlcikuIFRoZSB0cmF2ZWwgdGltZSBjYW5ub3QgYmUgcmVkdWNlZCBiZXlvbmQgdGhlIHNtYWxsZXN0IHBvc3NpYmxlIHRpbWUgQiBkZXNjcmliZWQgYWJvdmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldlIGFyZSBnaXZlbiBhIGNlcnRhaW4gYW1vdW50IG9mIG1vbmV5LiBXZSB3YW50IHRvIGRpc3RyaWJ1dGUgdGhpcyBtb25leSBhbG9uZyBkaWZmZXJlbnQgcm9hZHMgaW4gc3VjaCBhIHdheSB0aGF0IHRoZSB0aW1lIG5lZWRlZCB0byB0cmF2ZWwgZnJvbSB0aGUgY2l0eSAxIHRvIHRoZSBtb3N0IGRpc3RhbnQgY2l0eSAoYWZ0ZXIgYWxsIHRoZSByZXBhaXJzKSBpcyBhcyBzbWFsbCBhcyBwb3NzaWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBmaW5kIHRoaXMgc21hbGxlc3QgdGltZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBLLCAyICZsZTsgTiAmbGU7IDEwMCAwMDAsIDAgJmxlOyBLICZsZTsgMSAwMDAgMDAwLCB0aGUgbnVtYmVyIG9mIGNpdGllcyBhbmQgdGhlIHRvdGFsIGFtb3VudCBvZiBtb25leSAoaW4gZXVyb3MpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE4tMSBsaW5lcyBjb250YWlucyBmb3VyIGludGVnZXJzIFgsIFksIEEgYW5kIEIsIDAgJmxlOyBCICZsZTsgQSAmbGU7IDEwIDAwMC4gSXQgbWVhbnMgdGhhdCB0aGVyZSBpcyBhIHJvYWQgYmV0d2VlbiBjaXRpZXMgWCBhbmQgWSwgd2l0aCB0aGUgbnVtYmVycyBBIGFuZCBCIHJlcHJlc2VudGluZyB0aGUgY3VycmVudCB0aW1lIGFuZCB0aGUgbWluaW11bSB0aW1lIGFzIGRlc2NyaWJlZCBhYm92ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlciAmbmRhc2g7IHRoZSBtaW5pbXVtIHRpbWUgZnJvbSB0aGUgdGFzayBkZXNjcmlwdGlvbi4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=