eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 256 MiB

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

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

Input data

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

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

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

Output data

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

Examples

Input example #1
4 3
1 11 0 100 100 100
2 10 900 900 900 900
3 10 1000 1000 1000 0
4 9 0 0 1000 1000
Output example #1
1 3 4 
Input example #2
6 4
1 9 1000 1000 1000 1000
2 10 990 990 1000 1000
3 11 980 980 1000 1000
4 9 900 900 900 900
5 10 910 910 910 910
6 11 920 920 920 920
Output example #2
1 2 3 4 
Input example #3
12 8
176 10 24000 93790 7130 18970
661 10 58580 55440 84620 15590
447 11 22390 53560 26210 170
304 9 20310 95130 38070 75830
379 10 56990 17390 2350 1920
749 9 77280 65860 60930 56310
533 10 49330 84290 66180 34170
885 11 93770 95520 72250 89760
505 10 10680 63050 75080 15130
231 10 73310 57280 41650 65430
959 11 60070 27380 65980 36570
421 11 45830 29010 1420 25870
Output example #3
231 304 505 533 661 749 885 959 
Author Anton Tsypko
Source Всеукраїнська юніорська та дівоча олімпіади з інформатики 2021-2022, Другий відбірковий тур