第一行，三个正整数 $n,m,q(2\le n\le 20,1\le m\le 400,1\le q\le 10)$。
接下来 $m$ 行，每行三个正整数 ui,vi,ci(1≤ui,vi≤n,1≤ci≤20000)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​​(1≤u​i​​,v​i​​≤n,1≤c​i​​≤20000)，表示有一条从 uiu_iu​i​​ 到 viv_iv​i​​ 耗时为 cic_ic​i​​ 的有向边。
接下来 $q$ 行，每行四个正整数 si,ti,li,ri(1≤si,ti≤n,1≤li≤ri≤106)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)s​i​​,t​i​​,l​i​​,r​i​​(1≤s​i​​,t​i​​≤n,1≤l​i​​≤r​i​​≤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 并交货。