{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003e \u003c/p\u003e\r\n\u003ctable style\u003d\"border: 1px solid #2dd254; width: 100%; background-color: #d5d229;\" border\u003d\"1\"\u003e\r\n\u003ctbody\u003e\r\n\u003ctr\u003e\r\n\u003ctd style\u003d\"text-align: center;\" width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/MROADS/en/\"\u003eEnglish\u003c/a\u003e\u003c/td\u003e\r\n\u003ctd style\u003d\"text-align: center;\" width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/MROADS/vn/\"\u003eVietnamese\u003c/a\u003e\u003c/td\u003e\r\n\u003c/tr\u003e\r\n\u003c/tbody\u003e\r\n\u003c/table\u003e\r\n\u003cp\u003e\u003c/p\u003e\r\n\u003cp\u003eThe traffic network in a country consists of N cities (labeled with integers 1 to N) and N-1 roads connecting the cities. There is a unique path between each pair of different cities.\u003c/p\u003e\r\n\u003cp\u003e\u003cbr\u003eBecause of the many years of lazy maintenance the roads are pretty damaged and for each road two numbers A and B are known – the integer A represents the current time (in seconds) needed to travel along the road, and the integer B represents the smallest possible time (in seconds) needed to travel along this road if we repair all the damage.\u003c/p\u003e\r\n\u003cp\u003e\u003cbr\u003eWe want to invest a certain amount of money into road repair. For a particular road, the result will be proportional to the amount of invested money. For each euro invested in some road, the time needed to travel along that road will be reduced by one second (the amount of money invested in some road has to be an integer). The travel time cannot be reduced beyond the smallest possible time B described above.\u003c/p\u003e\r\n\u003cp\u003e\u003cbr\u003eWe are given a certain amount of money. We want to distribute this money along different roads in such a way that the time needed to travel from the city 1 to the most distant city (after all the repairs) is as small as possible.\u003c/p\u003e\r\n\u003cp\u003e\u003cbr\u003eWrite a program that will find this smallest time.\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of input contains two integers N and K, 2 ≤ N ≤ 100 000, 0 ≤ K ≤ 1 000 000, the number of cities and the total amount of money (in euros).\u003c/p\u003e\r\n\u003cp\u003e\u003cbr\u003eEach of the next N-1 lines contains four integers X, Y, A and B, 0 ≤ B ≤ A ≤ 10 000. It means that there is a road between cities X and Y, with the numbers A and B representing the current time and the minimum time as described above.\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eThe first and only line of output should contain a single integer – the minimum time from the task description.\u003c/p\u003e\r\n\u003ch3\u003eSample\u003c/h3\u003e\r\n\u003cpre\u003einput \u003cbr\u003e\u0026nbsp;\u003cbr\u003e3 200 \u003cbr\u003e1 2 200 100 \u003cbr\u003e2 3 450 250 \u003cbr\u003e\u0026nbsp;\u003cbr\u003eoutput \u003cbr\u003e\u0026nbsp;\u003cbr\u003e450\u003cbr\u003e\u003cbr\u003einput \u003cbr\u003e\u0026nbsp;\u003cbr\u003e5 11 \u003cbr\u003e1 2 10 5 \u003cbr\u003e1 3 3 2 \u003cbr\u003e1 4 9 6 \u003cbr\u003e3 5 7 3 \u003cbr\u003e\u0026nbsp;\u003cbr\u003eoutput \u003cbr\u003e\u0026nbsp;\u003cbr\u003e6\u003cbr\u003e\u003cbr\u003einput \u003cbr\u003e\u0026nbsp;\u003cbr\u003e11 12 \u003cbr\u003e1 2 7 5 \u003cbr\u003e1 3 20 15 \u003cbr\u003e2 4 10 8 \u003cbr\u003e2 5 5 3 \u003cbr\u003e2 6 6 2 \u003cbr\u003e4 7 3 0 \u003cbr\u003e4 8 7 2 \u003cbr\u003e5 9 8 4 \u003cbr\u003e5 10 9 8 \u003cbr\u003e5 11 6 5 \u003cbr\u003e\u0026nbsp;\u003cbr\u003eoutput \u003cbr\u003e\u0026nbsp;\u003cbr\u003e17\u003c/pre\u003e\r\n\u003cp\u003e \u003c/p\u003e\n\u003c/div\u003e"}}]}