Задача №111555. Петя отдыхает
Петя — большой фанат активного отдыха. Поэтому он решил активно отдохнуть от занятий в школе в течение N дней и посетить K праздничных мероприятий, проходящих в M разных городах. Петя начал свой отдых с того, что определил, за сколько дней он может добраться от каждого города до любого другого, а также распечатал и определил расписание всех мероприятий, которые он хотел бы посетить. В первый день Петя находится в первом городе, там же он должен находиться в день N, иначе его выгонят из школы.
Для каждого мероприятия известен день его начала, окончания, а также город, в котором оно проходит. Петя живёт полной жизнью, поэтому он посещает каждое мероприятие только целиком. Также Петя не может находиться на двух разных мероприятиях одновременно, даже если они проходят в одном городе. Однако, если два мероприятия проходят в одном городе, и первое заканчивается в тот же день, когда начинается второе, Петя может посетить оба. Также он может посетить мероприятие, начинающееся в день его приезда в город или заканчивающееся в день его отъезда из города.
Учитель информатики задал Вам задачку на дом: узнать, какое максимальное количество мероприятий может посетить Петя.
В первой строке даны три числа — количество дней активного отдыха N (1 ≤ N ≤ 106), количество городов M (1 ≤ M ≤ 250) и количество мероприятий K (1 ≤ K ≤ 5000).
В следующих M строках записаны по M чисел. j-ое число в i + 1-ой строчке "— целое положительное (за исключением диагональных элементов) количество дней Ai, j, необходимое, чтобы добраться от i-го города до j-го. Ai, j ≤ N. Диагональные элементы равны 0. Значение 1 в этой матрице означает, что Петя приедет в соответствующий город на следующий день после отъезда.
В следующих K строках записаны мероприятия. В каждой строке записаны три целых положительных числа Gi, Si, Fi "— номер города мероприятия, а также дни начала и окончания мероприятия соответственно. 1 ≤ Gi ≤ M, 1 ≤ Si ≤ Fi ≤ N.
Выведите единственное число — максимальное количество мероприятий, которые сможет посетить Петя.
Тесты к этой задаче состоят из четырех групп.
- Тесты 1-2. Тесты из условия, оцениваются в ноль баллов.
- Тесты 3-9. В тестах этой группы K ≤ 18. Эта группа оценивается в 15 баллов.
- Тесты 10-18. В тестах этой группы K ≤ 400. Эта группа оценивается в 25 баллов.
- Тесты 19-33. В тестах этой группы дополнительные ограничения отсутствуют. Решение оценивается в 60 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из второй и третьей групп.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
14 5 5 0 2 1 2 1 2 0 1 1 2 2 1 0 1 2 1 1 2 0 2 1 1 2 2 0 1 11 12 1 8 10 4 7 8 5 7 8 4 9 10
3
14 5 7 0 1 4 3 2 4 0 3 2 4 3 2 0 1 2 1 1 2 0 3 3 2 2 3 0 4 10 12 5 7 9 3 6 9 4 5 6 1 10 12 1 6 9 3 5 8
2