Авиакомпания предлагает авиабилеты из n аэропортов, пронумерованных от 1 до n. Время полета tij из аэропорта i в аэропорт j известно для всех пар i и j. Возможно tij ≠ tji из-за ветра или географического расположения. При посадке в аэропорту самолет должен быть осмотрен, прежде чем он сможет снова взлететь. Время осмотра составляет pi и зависит только от аэропорта, в котором проводится инспекция.

Имея набор из m предоставляемых рейсов, определите минимальное количество самолетов, которое должна купить авиакомпания. Авиакомпания может добавлять внеплановые рейсы для перемещения самолетов, если это уменьшит общее количество необходимых самолетов.

Входные данные

Первая строка содержит числа n и m (1 ≤ n, m ≤ 500). Следующая строка содержит n целых чисел p1, ..., pn (0 ≤ pi ≤ 106).

Каждая из следующих n строк содержит n целых чисел. j-ое число в строке i + 2 равно tij (0 ≤ tij ≤ 106). Гарантируется, что tii = 0 для всех i. Однако может иметь место tij ≠ tji при i ≠ j.

Каждая из следующих m строк содержит три целых числа si, fi и ti (1 ≤ si, fi ≤ n, si ≠ fi, 1 ≤ ti ≤ 106), указывающих на то что авиакомпания должна обеспечить полет из аэропорта si с точным временем вылета ti, следуя в точности в аэропорт fi.

Выходные данные

Выведите минимальное количество самолетов, которые должна приобрести авиакомпания, для обеспечения m требуемых рейсов.