当前没有测试数据。

Background

在一个战区中有 $n$ 个油井，编号为 $1, 2, ..., n$ 。有 $n – 1$ 条道路连接着这些油井，每条道路刚好连接两个油井，从任何一个油井，都可以通过这些道路到达其他任一个油井。每条道路的长度均为 $1$ 个单位。

Description

为保证该战区的安全，麒麟坦克每天要到所有的道路上巡逻。神州基地设在编号为 $1$ 的油井里，每天麒麟坦克总是从神州基地出发，最终又回到神州基地。 下图表示一个有 $8$ 个油井的战区，其中油井用圆表示（其中油井 $1$ 用黑色的圆表示），道路是连接这些圆的线段。为了遍历所有的道路，麒麟坦克需要走的距离为 $14$ 个单位，每条道路都需要经过两次。

为了减少总的巡逻距离，该战区准备在这些油井之间建立 $K$ 条新的道路，每条新道路可以连接任意两个油井。两条新道路可以在同一个油井会合或结束（见下面的图例（c） ）。一条新道路甚至可以是一个环，即，其两端连接到同一个油井。 由于资金有限，$K$ 只能是 $1$ 或 $2$。同时，为了不浪费资金，每天麒麟坦克必须经过新建的道路正好一次。 下图给出了一些建立新道路的例子：

在(a)中，新建了一条道路，总的距离是 $11$ 。在(b)中，新建了两条道路，总的巡逻距离是 $10$。在(c)中，新建了两条道路，但由于麒麟坦克要经过每条新道路正好一次，总的距离变为了 $15$。

试编写一个程序，读取油井间道路的信息和需要新建的道路数，计算出最佳 的新建道路的方案使得总的巡逻距离最小，并输出这个最小的巡逻距离。

Format

Input

Output

Samples

Limitation