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

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Бутявочная фермаограничение по времени на тест2 секундыограничение по памяти на тест64 мегабайтавводстандартный вводвыводстандартный вывод

У мальчика Димы есть своя бутявочная ферма. Скоро на ней вырастут 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

加入题单

上一题 下一题 算法标签: