DHONDT#9429
На початку грудня в нашій країні відбулися парламентські вибори. Азербайджан розділений на виборчих округів, від кожного з них обирається по депутатів. Кожен з виборців голосує за одну з декількох партій. Після голосування представники обираються за методом Д'Ондта (D'Hondt).
Згідно з цим методом, спочатку відбираються партії, що набрали не менше голосів. Кількість голосів кожної з таких партій потім ділиться на кожне число від до . Таким чином, кожній партії приписується раціональних чисел — назвемо їх «балами».
Першого з представників у регіоні обирають з партії з найбільшим балом, другого — з партії з другим за величиною балом, і так далі. Процедура триває, доки не будуть обрані всі місць. Примітка: завжди буде унікальний спосіб обрання представників, тобто не буде двох рівних балів.
Напишіть програму, яка, враховуючи загальну кількість виборців і кількість голосів, набраних кожною партією, визначає, скільки політиків було обрано представниками від кожної партії. Деякі партії набрали незначну кількість голосів і не будуть у вхідних даних — тому загальна кількість виборців може не дорівнювати сумі голосів у списку у вхідних даних.
Перший рядок містить натуральне число (1 \le X \le 2\ 500\ 000) — загальна кількість виборців у цьому регіоні.Другий рядок містить натуральне число (0 \le N \le 10) — кількість партій, які розглядаємо. Наступні рядків містять по два значення: ідентифікатор партії (велика літера англійського алфавіту) та кількість голосів (0 \le G \le 250\ 000), яку отримала ця партія.
Виведіть стільки рядків, скільки партій отримали щонайменше голосів. Для кожної такої партії виведіть ідентифікатор партії та кількість обраних представників від цієї партії. Рядки мають бути відсортовані за ідентифікаторами в алфавітному порядку.
Приклад 1
Приклад 2
Приклад 3