Для того, щоб потрапити на IV етап Всеукраїнської олімпіади з інформатики, n учням Києва потрібно написати чотири тури відбірково-тренувальних зборів.
Якщо склад команди міста Києва (позначимо це змінною m) на IV етап принаймні 7 учасників, то з кожної паралелі (9, 10, 11) має бути принаймні 2 учасники. Інакше з кожної паралелі має бути принаймні 1 учасник. Позначимо цю кількість змінною t. Тобто t=2, якщо m≥7, інакше t=1.
За кожний тур учасник отримує одне ціле число від 0 до 105. При чому це число ділиться на 10.
Визначимо для i-го учасника змінну ai — це сума балів за усі чотири турі, за виключенням найгіршого туру (з мінімальною кількістю балів). Іншими словами ai — це сума балів трьох найкращих турів.
Склад збірної міста Києва формується у два етапи:
Спочатку по кожній паралелі (9, 10, 11) усі учасники сортуються за спаданням ai. Кращі t учасників потрапляють у збірну. Тобто, на цьому етапі 3t учасників потрапляють у збірну.
Усі учасники, які не потрапили ще у збірну, сортуються разом (тобто, не окремо по класах, а разом). Вони сортуються за спаданням ai⋅ci. Де ci=1, якщо учасник виступає за 11 клас; ci=1.1, якщо учасник виступає за 10 клас; ci=1.2, якщо учасник виступає за 9 клас. Кращі m−3t учасники потрапляють у збірну.
Вам дано результати учасників. Визначте учасників, які потраплять у збірну.
PS. Реальний формат відбору з міста Києва трохи складніший, легенда була спрощена для полегшення задачі.
Перший рядок містить два цілі числа n та m (3≤n≤25, 3≤m≤20, m≤n).
Кожний з наступних n рядків містить по шість цілих чисел idi, gi, s1i, s2i, s3i, s4i (1≤idi≤1000, 9≤gi≤11, 0≤sji≤105, sji — ділиться на 10). idi — унікальний ідентифікаційний номер учасника. gi — клас виступу учасника. sji — кількість балів, який набрав i-ий учасник на j-му турі.
Гарантується, що на кожній паралелі буде принаймні t учасників. Гарантується, що на будь-якому етапу не буде пари учасників з однаковою кількістю балів. Тобто, гарантується, що алгоритм завжди зможе визначити учасників.
Виведіть ідентифікаційні номери учасників, які потрапили у збірні, у зростаючому порядку ідентифікаційних номерів.