Самый прибыльный период из предложенных

Есть прибыль магазина за n дней (бывают и убытки). Маркетолог предложил q периодов [l, r] (дни нумеруются с 1, границы включительно). Найдите период с наибольшей суммарной прибылью. Если таких несколько, выберите период с меньшим номером.

Ввод: в первой строке n и q (1 ≤ n, q ≤ 2500), во второй n чисел (|aᵢ| ≤ 10⁹), далее q строк по два числа l r (1 ≤ l ≤ r ≤ n).

Вывод: номер лучшего периода (с 1) и его прибыль через пробел.

Пример 1

Ввод:

5 3
3 -1 4 -1 5
1 2
2 4
1 5

Вывод:

3 10

Пример 2

Ввод:

3 2
-5 -5 -5
1 3
2 2

Вывод:

2 -5