Петя отдыхает
Петя — большой фанат активного отдыха. Поэтому он решил активно отдохнуть от занятий в школе в течение N дней и посетить K праздничных мероприятий, проходящих в M разных городах. Петя начал свой отдых с того, что определил, за сколько дней он может добраться от каждого города до любого другого, а также распечатал и определил расписание всех мероприятий, которые он хотел бы посетить. В первый день Петя находится в первом городе, там же он должен находиться в день N, иначе его выгонят из школы.
Для каждого мероприятия известен день его начала, окончания, а также город, в котором оно проходит. Петя живёт полной жизнью, поэтому он посещает каждое мероприятие только целиком. Также Петя не может находиться на двух разных мероприятиях одновременно, даже если они проходят в одном городе. Однако, если два мероприятия проходят в одном городе, и первое заканчивается в тот же день, когда начинается второе, Петя может посетить оба. Также он может посетить мероприятие, начинающееся в день его приезда в город или заканчивающееся в день его отъезда из города.
Учитель информатики задал Вам задачку на дом: узнать, какое максимальное количество мероприятий может посетить Петя.
Входные данные
В первой строке даны три числа — количество дней активного отдыха 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.
Выходные данные
Выведите единственное число — максимальное количество мероприятий, которые сможет посетить Петя.