Соня очень любит мороженое. Она ест его даже во время соревнований по программированию. Поэтому, девочка решила, что хочет открыть свои собственные магазины мороженого.

Соня живет в городе, в котором всего $$$n$$$ перекрестков и $$$n-1$$$ улиц. Все улицы — двусторонние и соединяют пары перекрестков. С любого перекрестка можно попасть в любой другой перекресток в городе, пройдя по одной или более улиц. Мэрия позволяет открывать магазины только на перекрестках, девочка не может открывать магазины посреди улиц, между перекрестками.

У Сони есть ровно $$$k$$$ друзей, которым она доверяет. Если она откроет магазин, один с её друзей должен там работать и смотреть, чтобы никто не ел мороженое не заплатив. Поскольку Соня не хочет пропускать важные соревнования по программированию, непосредственно в магазинах она работать не будет.

Соня хочет, чтобы все её магазины мороженого образовали простой путь длины $$$r$$$ ($$$1 \le r \le k$$$), то есть были расположены в различных перекрёстках $$$f_1, f_2, \dots, f_r$$$ и существовала улица между $$$f_i$$$ и $$$f_{i+1}$$$ для всех $$$i$$$ от $$$1$$$ до $$$r-1$$$.

Девочка заботится о потенциальных покупателях, поэтому, она также хочет минимизировать максимальное расстояние от перекрестков до ближайшего магазина мороженого. Расстояние между двумя перекрестками $$$a$$$ и $$$b$$$ равно сумме длин всех улиц, которые нужно пройти, чтобы попасть с перекрестка $$$a$$$ на перекресток $$$b$$$. Таким образом, девочка хочет минимизировать

$$$$$$\max_{a} \min_{1 \le i \le r} d_{a,f_i}$$$$$$,

где $$$a$$$ принимает значение всевозможных $$$n$$$ перекрёстков, $$$f_i$$$ — перекресток с $$$i$$$-м магазином Сони, а $$$d_{x,y}$$$ — расстояние между перекрестками $$$x$$$ и $$$y$$$.

Соня неуверенна, что сможет найти оптимальные местоположения магазинов, поэтому, просит вас помочь ей открыть не более $$$k$$$ магазинов, которые образуют простой путь, и максимальное расстояние от произвольного перекрестка города до ближайшего магазина минимально.