Задачка на алгоритмы) Кому интересно и не жалко времени, заходите

В общем, решил попробовать пройти тестирование в одну компанию, не буду называть какую. Мне прислали такую интересную задачку. Задачку эту я решил, перебрал много переменных значений, ответ получается правильный. Но их валидатор говорит что программа выполняется слишком долго(это так, если в значение N- количество счетов передавать сто тысяч счетов, проверял, 13 секунд программа работает, надо видимо за секунду чтобы работала). Мне очень интересно было бы увидеть ваш вариант решения). В конце напишу свой вариант решения. Условия задачи: Ограничение времени, с 1 Ограничение памяти, МБ 64 Общее число попыток отправки 15 Петр Васильевич, директор ОАО "Рога и рога", собирается раздать премию всем менеджерам компании, он добрый и честный человек, поэтому хочет соблюсти следующие условия: премия должна быть равной для всех менеджеров должна быть максимально возможной и целой должна быть выдана одной транзакцией с одного счета для каждого менеджера, без использования нескольких счетов для отправки одной премии У Петра Васильевича открыто N корпоративных счетов, на которых лежат разные суммы денег Cn, а в компании работает M менеджеров. Необходимо выяснить максимальный размер премии, которую можно отправить с учетом условий. Если денег на счетах компании не хватит на то, чтобы выдать премию хотя бы по 1 у.е. - значит премии не будет, и нужно вывести 0. Входные данные (поступают в стандартный поток ввода) Первая строка - целые числа N и M через пробел (1≤N≤100 000, 1≤M≤100 000) Далее N строк, на каждой из которых одно целое число Cn (0≤Cn≤100 000 000) Проверка входных данных и обработка неправильных данных на входе не нужна, тестовые данные для проверки гарантированно подходят под описание выше Выходные данные (ожидаются в стандартном потоке вывода) Одно целое число, максимально возможная премия Пример 1 Ввод: 3 6 453 220 601 Вывод: 200 Пример 2 Ввод: 2 100 99 1 Вывод: 1 Пример 3 Ввод: 2 100 98 1 Вывод: 0 Мой вариант:

import java.util.Scanner;
class Main {
  public static void main(String[] args) {
        long pays = 0L; // максимальное количество выплаты на одного менеджера
        try {
            Scanner scan = new Scanner(System.in);
            String str = scan.nextLine();  //считываем строку
            int n = Integer.parseInt(str.split(" ")[0]); //распарсили первых два числа
            int m = Integer.parseInt(str.split(" ")[1]);
            long[] acc = new long[n]; // создаем массив для хранения значения каждого корпоративного счета
            long summa = 0L; // общая сумма со всех счетов
            for (int i = 0; i < acc.length; i++) { // считываем все счета и помещаем их в массив плюс находим общую сумму на всех счетах
                acc[i] = Long.parseLong(scan.nextLine());
                summa += acc[i];
            }

            if(summa > 0 && m > 0) pays = summa/m; //здесь получаем максимально возможную выплату на каждого менеджера
            if(pays != 0) {
                while(true) {   // а здесь как раз самая долгая часть выполнения программы
                    int g = 0; // переменная для хранения количества менеджеров для которых хватит выплатить денег с одного счета
                    for (int i = 0; i < acc.length; i++) {   // перебираем все счета
                        g += acc[i] / pays; // узнаем скольким менеджерам хватит выплатить указанное в pays количество денег
                    }
                    if(g >= m) break; // если всем менеджерам хватает данной выплаты то завершаем программу
                    else pays--; // если не всем менеджерам хватает выплаты то сумму выплат уменьшаем на единицу
                }
            }
        } catch (Exception ex) {}
        finally {
            System.out.println(pays); // выводим результат
        }
   }
}