eolymp
bolt
Try our new interface for solving problems
Məsələlər

Петя отдыхает

Петя отдыхает

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Петя — большой фанат активного отдыха. Поэтому он решил активно отдохнуть от занятий в школе в течение N дней и посетить K праздничных мероприятий, проходящих в M разных городах. Петя начал свой отдых с того, что определил, за сколько дней он может добраться от каждого города до любого другого, а также распечатал и определил расписание всех мероприятий, которые он хотел бы посетить. В первый день Петя находится в первом городе, там же он должен находиться в день N, иначе его выгонят из школы.

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

Учитель информатики задал Вам задачку на дом: узнать, какое максимальное количество мероприятий может посетить Петя.

Giriş verilənləri

В первой строке даны три числа — количество дней активного отдыха N (1 ≤ N ≤ 10^6), количество городов M (1 M 250) и количество мероприятий K (1 ≤ K ≤ 5000).

В следующих M строках записаны по M чисел. j-ое число в i+1-ой строчке — целое положительное (за исключением диагональных элементов) количество дней A_{i, j}, необходимое, чтобы добраться от i-го города до j-го. A_{i, j} ≤ N. Диагональные элементы равны 0. Значение 1 в этой матрице означает, что Петя приедет в соответствующий город на следующий день после отъезда.

В следующих K строках записаны мероприятия. В каждой строке записаны три целых положительных числа G_i, S_i, F_i — номер города мероприятия, а также дни начала и окончания мероприятия соответственно.

1 ≤ G_i ≤ M, 1 ≤ S_i ≤ F_i ≤ N.

Çıxış verilənləri

Выведите единственное число — максимальное количество мероприятий, которые сможет посетить Петя.

Nümunə

Giriş verilənləri #1
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
Çıxış verilənləri #1
3