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

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

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

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

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

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

1. Спочатку по кожній паралелі ($9$, $10$, $11$) усі учасники сортуються за спаданням $a_i$. Кращі $t$ учасників потрапляють у збірну. Тобто, на цьому етапі $3t$ учасників потрапляють у збірну.

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

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

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

Giriş verilənləri

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

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

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

Çıxış verilənləri

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

Nümunələr