Shi's mansion is almost complete and now he is choosing where to put his Really Spectacular Throne made of Imperial Gold (TOIRE). In order to do that, he asked one of his minions to suggest him m rooms where he could put his TOIRE. In his mansion, there are n rooms, each of which has a level of filthiness si, known by the minion.
The minion is responsible for cleaning the TOIRE so he will to suggest the rooms in a way that cleaning the TOIRE will be easier. Shi will choose the room where he will put the TOIRE randomly between the rooms suggested by the minion.
In the worst case, what will be the level of filthiness of the TOIRE?
The input starts with two integers n (1 ≤ n ≤ 106) and m (1 ≤ m ≤ n), indicating the number of rooms and the number of suggestions. The line is followed by n lines, containing an integer that is the level of filthiness si (0 ≤ si ≤ 109) of each room.
Print one integer indicating the level of filthiness of the TOIRE in the worst case.
## Input
The input starts with two integers n (1 ≤ n ≤ 106) and m (1 ≤ m ≤ n), indicating the number of rooms and the number of suggestions. The line is followed by n lines, containing an integer that is the level of filthiness si (0 ≤ si ≤ 109) of each room.
## Output
Print one integer indicating the level of filthiness of the TOIRE in the worst case.
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the number of cities and roads, respectively.
Let $ G = (V, E) $ be an undirected weighted graph with $ V = \{1, \dots, n\} $ (cities) and $ E \subseteq V \times V $ (roads), where each edge $ (x, y) \in E $ has weight $ c_{xy} \in \mathbb{Z}^+ $ (tax).
Let $ B_i $ denote the bus initially located at city $ i $, carrying driver $ i $, for $ i \in \{1, \dots, n\} $.
Let $ D = \{1, \dots, n\} $ be the set of drivers.
**Constraints**
1. Each bus $ B_i $ starts at city $ i $ with driver $ i $.
2. A **DRIVE** operation $ \text{DRIVE}(b, x, y) $ is valid iff:
- Bus $ b $ is currently at city $ x $,
- Bus $ b $ contains at least one driver,
- Edge $ (x, y) \in E $ exists.
- Cost: $ c_{xy} $.
3. A **MOVE** operation $ \text{MOVE}(d, x, y) $ is valid iff:
- Driver $ d $ is currently in bus $ x $,
- Buses $ x $ and $ y $ are located at the same city.
- Cost: $ 0 $.
4. Each driver may perform at most 25 **MOVE** operations.
5. Goal: All drivers must be in the same bus.
**Objective**
Find the minimal total cost of **DRIVE** operations (since **MOVE** operations are free) to consolidate all drivers into one bus, subject to the driver move limit, and output a sequence of operations achieving this minimum.
Let $ \mathcal{P} $ be the set of all possible sequences of DRIVE and MOVE operations satisfying constraints.
Minimize:
$$
\sum_{\text{DRIVE}(b, x, y) \in \mathcal{P}} c_{xy}
$$
subject to:
- All drivers end in one bus,
- Each driver participates in at most 25 MOVE operations.