Задача №114280. Бутявочная ферма
У мальчика Димы есть своя бутявочная ферма. Скоро на ней вырастут N бутявок, и Диме надо будет отвезти их на рынок продавать.
Бутявок надо перевозить в стеклянных банках. Если какая-то банка будет заполнена не полностью, то бутявки в этой банке закузявятся, поэтому каждую банку надо заполнять полностью.
Дима может покупать банки на стеклозаводе. Завод производит K типов банок, банки i -го типа вмещают a i бутявок каждая. Дима может заказать на заводе сколько угодно банок, но, чтобы получить оптовую скидку, он должен заказывать банки только какого-то одного типа.
Естественно, Дима хочет заказать банки так, чтобы можно было каждую банку заполнить бутявками доверху и отвезти на рынок; если при этом какие-то бутявки не влезут, то Дима оставит этих бутявок на ферме.
Определите, сколько банок и какого типа должен заказать Дима, чтобы увезти на рынок как можно больше бутявок.
Первая строка входных данных содержит два целых числа N и K — количество бутявок, которые вырастут у Димы на ферме, и количество типов банок, которые производит стеклозавод ( 0 ≤ N ≤ 10 18 , 1 ≤ K ≤ 10 5 ).
Во второй строке находятся K целых чисел a 1 , a 2 , ..., a K — вместимости каждого типа банок ( 1 ≤ a i ≤ 10 18 для всех i ).
Выведите два числа — номер типа банок, которые должен заказать Дима, и их количество. Типы банок нумеруются от 1 до K в том порядке, как они описаны во входных данных.
Если верных ответов несколько, вы можете вывести любой из них.
В тестах общей стоимостью 25 баллов все числа во входных данных не будут превосходить 1000 . В тестах общей стоимостью 50 баллов все числа во входных данных не будут превосходить 10 5 .
19 3 5 4 10
2 4
28 3 5 6 30
1 5