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

Execution time limit is 1 second

Runtime memory usage limit is 256 megabytes

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

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

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

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

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

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

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

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

Input

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

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

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

Output

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

Examples

Input #1

Answer #1

Input #2

Answer #2

Input #3

Answer #3