Відбір на олімпіаду#11024

Відбір на олімпіаду

1 second

256 megabytes

Easy

Для того, щоб потрапити на IV етап Всеукраїнської олімпіади з інформатики, $n$ учням Києва потрібно написати чотири тури відбірково-тренувальних зборів.

Якщо склад команди міста Києва (позначимо це змінною $m$ ) на IV етап принаймні $7$ учасників, то з кожної паралелі ( $9$ , $10$ , $11$ ) має бути принаймні $2$ учасники. Інакше з кожної паралелі має бути принаймні $1$ учасник. Позначимо цю кількість змінною $t$ . Тобто $t = 2$ t=2, якщо $m \geq 7$ m\geq 7, інакше $t = 1$ t=1.

За кожний тур учасник отримує одне ціле число від $0$ до $1 0^{5}$ 10^5. При чому це число ділиться на $10$ .

Визначимо для $i$ -го учасника змінну $a_{i}$ a_i — це сума балів за всі чотири тури, за виключенням найгіршого туру (з мінімальною кількістю балів). Іншими словами $a_{i}$ a_i — це сума балів трьох найкращих турів.

Склад збірної міста Києва формується у два етапи:

Спочатку по кожній паралелі ( $9$ , $10$ , $11$ ) усі учасники сортуються за спаданням $a_{i}$ a_i. Кращі $t$ учасників потрапляють у збірну. Тобто, на цьому етапі $3 t$ учасників потрапляють у збірну.
Усі учасники, які не потрапили ще у збірну, сортуються разом (тобто, не окремо по класах, а разом). Вони сортуються за спаданням $a_{i} \cdot c_{i}$ a_i \cdot c_i. Де $c_{i} = 1$ c_i = 1, якщо учасник виступає за $11$ клас; $c_{i} = 1.1$ c_i=1.1, якщо учасник виступає за $10$ клас; $c_{i} = 1.2$ c_i=1.2, якщо учасник виступає за $9$ клас. Кращі $m - 3 t$ m-3t учасники потрапляють у збірну.

Вам дано результати учасників. Визначте учасників, які потраплять у збірну.

PS. Реальний формат відбору з міста Києва трохи складніший, легенда була спрощена для полегшення задачі.

Input

Перший рядок містить два цілі числа $n$ та $m$ ( $3 \leq n \leq 25$ 3 \leq n \leq 25, $3 \leq m \leq 20$ 3 \leq m \leq 20, $m \leq n$ m \leq n).

Кожний з наступних $n$ рядків містить по шість цілих чисел $i d_{i}$ id_i, $g_{i}$ g_i, $s_{1 i}$ s_{1i}, $s_{2 i}$ s_{2i}, $s_{3 i}$ s_{3i}, $s_{4 i}$ s_{4i} ( $1 \leq i d_{i} \leq 1000$ 1 \leq id_i \leq 1000, $9 \leq g_{i} \leq 11$ 9 \leq g_i \leq 11, $0 \leq s_{j i} \leq 1 0^{5}$ 0 \leq s_{ji} \leq 10^5, $s_{j i}$ s_{ji} — ділиться на $10$ ). $i d_{i}$ id_i — унікальний ідентифікаційний номер учасника. $g_{i}$ g_i — клас виступу учасника. $s_{j i}$ s_{ji} — кількість балів, яку набрав $i$ -ий учасник на $j$ -му турі.

Гарантується, що на кожній паралелі буде принаймні $t$ учасників. Гарантується, що на будь-якому етапу не буде пари учасників з однаковою кількістю балів. Тобто, гарантується, що алгоритм завжди зможе визначити учасників.

Output

Виведіть ідентифікаційні номери учасників, які потрапили у збірну, у зростаючому порядку ідентифікаційних номерів.

Examples

Example 1

Example 2

Example 3