408700: GYM103265 C Бутявочная ферма

У мальчика Димы есть своя бутявочная ферма. Скоро на ней вырастут N бутявок, и Диме надо будет отвезти их на рынок продавать.

Бутявок надо перевозить в стеклянных банках. Если какая-то банка будет заполнена не полностью, то бутявки в этой банке закузявятся, поэтому каждую банку надо заполнять полностью.

Дима может покупать банки на стеклозаводе. Завод производит K типов банок, банки i-го типа вмещают a_i бутявок каждая. Дима может заказать на заводе сколько угодно банок, но, чтобы получить оптовую скидку, он должен заказывать банки только какого-то одного типа.

Естественно, Дима хочет заказать банки так, чтобы можно было каждую банку заполнить бутявками доверху и отвезти на рынок; если при этом какие-то бутявки не влезут, то Дима оставит этих бутявок на ферме.

Определите, сколько банок и какого типа должен заказать Дима, чтобы увезти на рынок как можно больше бутявок.

Первая строка входных данных содержит два целых числа N и K — количество бутявок, которые вырастут у Димы на ферме, и количество типов банок, которые производит стеклозавод (0 ≤ N ≤ 10¹⁸, 1 ≤ K ≤ 10⁵).

Во второй строке находятся K целых чисел a₁, a₂, ..., a_K — вместимости каждого типа банок (1 ≤ a_i ≤ 10¹⁸ для всех i).

Выведите два числа — номер типа банок, которые должен заказать Дима, и их количество. Типы банок нумеруются от 1 до K в том порядке, как они описаны во входных данных.

Если верных ответов несколько, вы можете вывести любой из них.

В тестах общей стоимостью 25 баллов все числа во входных данных не будут превосходить 1000. В тестах общей стоимостью 50 баллов все числа во входных данных не будут превосходить 10⁵.

19 3
5 4 10

2 4

28 3
5 6 30

1 5