题目描述

一张 $n$ 个点 $m$ 条有向边的图上，有 $q$ 个配送需求，需求的描述形式为 $( s_i , t_i , l_i , r_i )$，即需要从点 $s_i$ 送到 $t_i$，在时刻 $l_i$ 之后（包括 $l_i$）可以在 $s_i$ 领取货物，需要在时刻 $r_i$ 之前（包括 $r_i$）送达 $t_i$，每个任务只需完成一次。

图上的每一条边均有边权，权值代表通过这条边消耗的时间。在时刻 $0$ 有一个工作人员在点 $1$ 上，求他最多能完成多少个配送任务。

在整个过程中，可以认为领货跟交货都是不消耗时间的，时间只花费在路程上。当然在一个点逗留也是允许的。

输入格式

第一行，三个正整数 $n , m , q$（$2\leq n\leq 20, 1\leq m\leq 400, 1\leq q\leq 10$）。

接下来 $m$ 行，每行三个正整数 $u_i , v_i , c_i$（$1\leq u_i,v_i\leq n, 1\leq c_i\leq 20000$），表示有一条从 $u_i$ 到 $v_i$ 耗时为 $c_i$ 的有向边。

接下来 $q$ 行，每行四个正整数 $s_i , t_i , l_i , r_i$（$1\leq s_i,t_i\leq n, 1\leq l_i\leq r_i\leq 10^6$），描述一个配送任务。

输出格式

一个整数，表示最多能完成的任务数量。

样例

输入

5 4 3
1 2 1
2 3 1
3 4 1
4 5 1
1 2 3 4
2 3 1 2
3 4 3 4

输出

2

工作人员可以在时刻 $1$ 到达点 $2$，领取第二个货物后在时刻 $2$ 到达点 $3$ 后交货，逗留到时刻 $4$，领取第三个货物，在时刻 $4$ 到达点 $4$ 并交货。