本题没有可用的提交语言。

参考翻译

题目描述

$Lily$ 经营一家维修公司，负责服务城市的 $Q$ 区块。有一天，公司收到了 $M$ 个维修任务，第 $i$ 个任务发生在区块 $p$，有一个截止时间 $t$，在任何一个维修员到达时也是其开始时间，并且需要单个维修员 $d$ 时间来完成。维修员独自完成所有任务，并且必须在一个任务完成前才能开始下一个任务。手握城市地图，$Lily$ 想知道当天任务需要分配的最少维修员数量。

输入

输入包含多个测试用例。每个测试用例以包含 $Q$ 和 $M（0 < Q ≤ 20, 0 < M ≤ 200）$的一行开头。然后跟随着 Q 行，每行包含 $Q$ 个整数，这些整数表示一个 $Q × Q$ 矩阵$Δ = {δ _{ij}}$，其中 $δ_{ij}$ 表示第 $i$ 个和第 $j$ 个区块之间有一条双向道路，从一个端点到另一个端点需要 $δ_{ij}$ 时间。如果 $δ_{ij}$ = −1，则这样的道路不存在。该矩阵是对称的，并且它的所有对角线元素都是零。矩阵下方是 $M$ 行，描述了维修任务。第 $i$ 行的这些行包含 $p、t$ 和 $d$。在最后一个测试用例之后，有两行零。

输出

对于每个测试用例，输出一行，包含必须分配的最少维修人员数量。

1 2
0
1 1 10
1 5 10
0 0

2