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