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

Водитель школьного автобуса Отто живет на улице из `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`). За одну единицу времени Отто проезжает между двумя соседними домами. Посадка в автобус происходит мгновенно.

Вывести одно целое число – максимальную суммарную важность школьников, которых Отто сможет доставить в школу.

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

125

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

172