Соня очень любит мороженое. Она ест его даже во время соревнований по программированию. Поэтому, девочка решила, что хочет открыть свои собственные магазины мороженого.
Соня живет в городе, в котором всего \(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\) магазинов, которые образуют простой путь, и максимальное расстояние от произвольного перекрестка города до ближайшего магазина минимально.