CF1687B.Railway System

As for the technology in the outside world, it is really too advanced for Gensokyo to even look up to.

—Yasaka Kanako, Symposium of Post-mysticism

This is an interactive problem.

Under the direct supervision of Kanako and the Moriya Shrine, the railway system of Gensokyo is finally finished. GSKR (Gensokyo Railways) consists of $n$ stations with $m$ bidirectional tracks connecting them. The $i$-th track has length $l_i$ ($1\le l_i\le 10^6$). Due to budget limits, the railway system may not be connected, though there may be more than one track between two stations.

The value of a railway system is defined as the total length of its all tracks. The maximum (or minimum) capacity of a railway system is defined as the maximum (or minimum) value among all of the currently functional system's full spanning forest.

In brief, full spanning forest of a graph is a spanning forest with the same connectivity as the given graph.

Kanako has a simulator only able to process no more than $2m$ queries. The input of the simulator is a string $s$ of length $m$, consisting of characters 0 and/or 1. The simulator will assume the $i$-th track functional if $s_i=$ 1. The device will then tell Kanako the maximum capacity of the system in the simulated state.

Kanako wants to know the the minimum capacity of the system with all tracks functional with the help of the simulator.

The structure of the railway system is fixed in advance. In other words, the interactor is not adaptive.

至于外界的技术，其先进程度对幻想乡而言，简直高不可攀。

——八坂神奈子，《后神秘主义座谈会》

这是一道交互式题目。

在神奈子与守矢神社的直接监督下，幻想乡铁路系统终于建成。GSKR（幻想乡铁路公司）由 $n$ 个车站和连接它们的 $m$ 条双向轨道组成。第 $i$ 条轨道长度为 $l_i$（$1\le l_i\le 10^6$）。受限于预算，该铁路系统未必连通，且两站之间可能存在多条轨道。

一个铁路系统的价值定义为它所有轨道长度的总和。一个当前正常运行的铁路系统的最大（或最小）容量，定义为该系统所有全生成森林（full spanning forest）中价值的最大值（或最小值）。

简言之，一个图的全生成森林是指与其具有相同连通性的生成森林。

神奈子拥有一台模拟器，最多支持 $2m$ 次查询。每次查询向模拟器输入一个长度为 $m$ 的字符串 $s$，其中每个字符为 0 或 1。模拟器将假设：若 $s_i = \texttt{1}$，则第 $i$ 条轨道处于功能状态。随后，设备会返回该模拟状态下系统的最大容量。

神奈子希望借助该模拟器，求出当所有轨道均正常运行时，该系统的最小容量。

铁路系统的结构是预先固定的，即交互器是非自适应的。

The first and only line of input contains two integers $n,m$ ($2 \leq n \leq 200$, $1\le m \le 500$) — the number of stations and tracks.

输入仅有一行，包含两个整数 $n,m$（$2 \leq n \leq 200$，$1\le m \le 500$）——分别表示车站数量和轨道数量。

Here is the graph of the example, satisfying $l_i=i$.

以下是示例的图，满足 $l_i=i$。