Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Нота «ДО»

(Время: 2 сек. Память: 32 Мб Сложность: 57%)

У Димы есть несколько хобби: он любит работать в саду, увлекается геометрией, а недавно стал осваивать музыкальную грамоту. В саду он больше времени уделяет деревьям, в геометрии он неравнодушен к отрезкам, а при освоении нот в музыкальной школе ему больше всего понравилась нота «ДО».Сегодня пришло время изучать информатику. На занятиях Дима получил массив из N чисел, на котором он должен сделать Q запросов. Каждый запрос состоит из двух целых чисел L и R. Ответом на запрос служит сумма чисел с индексами от L до R включительно в исходном массиве.

Дима заметил, что уровень его радости от процесса вычислений напрямую зависит от суммарного значения всех ответов на запросы. Учитывая то, что Дима может изменить порядок элементов в массиве произвольным образом, он захотел вычислить значение максимально возможной суммы результатов всех запросов, которую он может получить таким образом.

Помогите вычислить Диме это значение!

Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа N и Q (1 ≤ N, Q ≤ 105).

Во второй строке находится N целых чисел Ai, задающих элементы массива (1 ≤ Ai ≤108).

В последующих Q строках находятся пары чисел L и R (1 ≤ L ≤ R ≤ N), обозначающие границы отрезка, на котором нужно вычислять сумму элементов.

Выходные данные

В единственной строке выходного файла OUTPUT.TXT выведите единственное целое число – максимально возможную сумму результатов всех запросов, которую Дима может получить.

Пример

INPUT.TXTOUTPUT.TXT
13 4
7 3 1
1 3
2 3
3 3
2 2
31

Система оценки

Решения, работающие только для N, Q ≤ 1000, будут оцениваться в 50 баллов.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 Седьмая командная олимпиада
 A. Доставка суши
 B. Нота «ДО»
 C. Строка
 D. Две строки
 E. Сдача
 F. Турист
 G. Через k секунд
 H. Компьютерная игра

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru