eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Телебашта

Телебашта

Ліміт часу 3 секунди
Ліміт використання пам'яті 64 MiB

Телевізійна компанія має план країни, на якому вказано розміщення міст і населення кожного міста. Вони хочуть встановити телебашту так, щоб найбільше число жителів змогло дивитись телепередачі. Сигнал від телебашти приймається у всіх точках, які знаходяться на відстані не більше R від неї. Вам пропонується написати програму, яка визначає точку, де потрібно встановити телебашту. При цьому встанавлювати телебашту (із міркувань безпеки самої телебашти) можна лише у якомусь з міст.

Вхідні дані

У вхідному файлі записані спочатку радіус 0R10000 дії телебашти та кількість міст N (1N100) у країні. Далі записано інформацію про кожне місто – координати (x, y) та населення. Всі координати - цілі числа, які не превищують по модулю 10000, а кількість жителів – невід'ємне число, яке не перевищує міліон чоловік.

Вихідні дані

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

Приклад

Вхідні дані #1
1 4
0 1 4
0 0 5
1 0 3
1 1 2
Вихідні дані #1
12 2