printРабочее место участника

printЗадачи

2403. Школьный автобус

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Водитель школьного автобуса Отто живет на улице из `N` домов в доме с номером `K`. В 7:00 `M` школьников выходят из своих домов и ожидают некоторое время на улице, а Отто выезжает из своего дома. Если автобус не приезжает к моменту, когда школьник устанет ждать, он возвращается домой и ложится досыпать. Школьники отранжированы по важности (отличник имеет важность 100, хулиган – 1), и Отто может выбрать порядок, в котором он объезжает улицу, чтобы собрать школьников с максимальной суммарной важностью.
Напишите программу, которая поможет Отто спланировать маршрут автобуса.
Первая строка ввода содержит три целых числа – количество домов на улице `N`, номер дома `K`, в котором живет Отто, (`1\ ≤\ K\ ≤\ N\ ≤\ 1000`) и количество школьников `M` (`1\ ≤\ M\ ≤\ 100`). Далее следует `M` строк, в каждой строке по три целых числа – номер дома `A_i` (`1\ ≤\ A_i\ ≤\ N`, `A_i\ <\ A_{i+1}`, `A_i\ ≠\ K`), в котором живет школьник, важность его доставки в школу `B_i` (`1\ ≤\ B_i\ ≤\ 100`) и время ожидания автобуса `T_i` (`1\ ≤\ T_i\ ≤\ 2000`). За одну единицу времени Отто проезжает между двумя соседними домами. Посадка в автобус происходит мгновенно.
Вывести одно целое число – максимальную суммарную важность школьников, которых Отто сможет доставить в школу.

Пример ввода 1

10 5 4
1 100 4
3 5 7
7 20 12
10 100 24

Пример вывода 1

125

Пример ввода 2

20 8 7
1 35 14
4 57 1
6 32 2
9 94 28
14 78 8
15 8 1
17 55 3

Пример вывода 2

172
Пояснение к примеру 1:
Отто едет к дому №3, затем к дому №7 и к дому №10, затем везёт трех школьников в школу.
Отто не успевает доехать до дома №1 от стартового дома №5, чтобы забрать школьника.

Пояснение к примеру 2:
Отто едет по маршруту `8->9->14->`школа
loading