Петя --- большой фанат активного отдыха. Поэтому он решил активно отдохнуть от занятий в школе в течение \textbf{N }дней и посетить \textbf{K} праздничных мероприятий, проходящих в \textbf{M} разных городах. Петя начал свой отдых с того, что определил, за сколько дней он может добраться от каждого города до любого другого, а также распечатал и определил расписание всех мероприятий, которые он хотел бы посетить. В первый день Петя находится в первом городе, там же он должен находиться в день \textbf{N}, иначе его выгонят из школы. Для каждого мероприятия известен день его начала, окончания, а также город, в котором оно проходит. Петя живёт полной жизнью, поэтому он посещает каждое мероприятие только целиком. Также Петя не может находиться на двух разных мероприятиях одновременно, даже если они проходят в одном городе. Однако, если два мероприятия проходят в одном городе, и первое заканчивается в тот же день, когда начинается второе, Петя может посетить оба. Также он может посетить мероприятие, начинающееся в день его приезда в город или заканчивающееся в день его отъезда из города. Учитель информатики задал Вам задачку на дом: узнать, какое максимальное количество мероприятий может посетить Петя. \InputFile В первой строке даны три числа --- количество дней активного отдыха \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^6}), количество городов \textbf{M }(\textbf{1 }≤ \textbf{M }≤ \textbf{250}) и количество мероприятий \textbf{K} (\textbf{1} ≤ \textbf{K} ≤ \textbf{5000}). В следующих \textbf{M} строках записаны по \textbf{M} чисел. \textbf{j}-ое число в \textbf{i+1}-ой строчке --- целое положительное (за исключением диагональных элементов) количество дней \textbf{A_\{i, j\}}, необходимое, чтобы добраться от \textbf{i}-го города до \textbf{j}-го. \textbf{A_\{i, j\}} ≤ \textbf{N}. Диагональные элементы равны \textbf{0}. Значение \textbf{1} в этой матрице означает, что Петя приедет в соответствующий город на следующий день после отъезда. В следующих \textbf{K} строках записаны мероприятия. В каждой строке записаны три целых положительных числа \textbf{G_i}, \textbf{S_i}, \textbf{F_i} --- номер города мероприятия, а также дни начала и окончания мероприятия соответственно. \textbf{1} ≤ \textbf{G_i} ≤ \textbf{M}, \textbf{1} ≤ \textbf{S_i} ≤ \textbf{F_i} ≤ \textbf{N}. \OutputFile Выведите единственное число --- максимальное количество мероприятий, которые сможет посетить Петя.