#P18369. Projects

Projects

Projects

你是一家软件公司的经理。今天,公司的 nn 名程序员需要完成 mm 个项目。

项目 ii 只能由程序员 aia_i 和 bib_i 完成。程序员 aia_i 独自完成该项目需要 tit_i 个时间单位;若 ai≠bia_i\ne b_i,程序员 bib_i 在这个项目上的工作速度只有 aia_i 的一半。两人可以分工:aia_i 选择一个实数 xix_i,满足 0≤xi≤ti0\le x_i\le t_i,在该项目上工作 xix_i 个时间单位;剩余部分由 bib_i 完成,需要 2(ti−xi)2(t_i-x_i) 个时间单位。

若 ai=bia_i=b_i,则该项目只能由这一人独自完成,需要 tit_i 个时间单位。

同一项目的两位程序员可以独立工作:既可以同时工作,也可以在完全不同的时段工作。每名程序员在任意时刻只能处理一个项目,其总工作时间等于他在各项目上花费的时间之和。切换项目所需的时间忽略不计。所有程序员今天同时开始工作。

有些程序员赶时间,希望尽早离开。你尚不知道具体哪些人赶时间,因此需要考虑 qq 个互相独立的情形。每个情形指定一个非空的赶时间程序员集合。

对于每个情形,求最小的实数 TT,使你能够安排工作,最终完成所有项目,并使每名赶时间的程序员总工作时间都不超过 TT。其余程序员的工作时间没有上限。

可以证明答案一定是有理数。请将答案写成最简分数。

输入格式

第一行包含三个整数 n,m,qn,m,q,分别表示程序员数、项目数和情形数。

接下来 mm 行,每行包含三个整数 ai,bi,tia_i,b_i,t_i,描述一个项目。不同项目允许具有相同的 ai,bia_i,b_i,也允许 ai=bia_i=b_i。

接下来 qq 行,每行包含一个长度为 nn 的二进制字符串 sis_i。第 jj 个字符为 1 表示程序员 jj 在该情形中赶时间,为 0 表示他不赶时间。每个字符串至少包含一个 1。

输出格式

输出 qq 行。第 ii 行输出该情形的最小可能工作时间上限,格式为 x/y,其中 gcd⁡(x,y)=1\gcd(x,y)=1 且 y>0y>0。答案为零时输出 0/1。

数据范围

  • 1≤n≤131\le n\le13;
  • 1≤m≤2001\le m\le200;
  • 1≤q≤100001\le q\le10000;
  • 1≤ai,bi≤n1\le a_i,b_i\le n;
  • 1≤ti≤10000001\le t_i\le1000000。

输入只有一组数据;qq 个情形分别独立考虑。

样例输入 1

5 7 7
2 1 2
2 2 1
3 2 3
3 4 5
4 3 2
1 5 7
1 5 7
10000
01000
00110
11100
11111
01111
01111

样例输出 1

0/1
1/1
4/1
18/7
28/3
19/4
19/4

样例说明

第一个情形中,程序员 1 可以立即离开,其余人能够完成全部项目。

第二个情形中,程序员 2 必须独自完成第二个项目,需要 1 个时间单位。

第三个情形中,程序员 4 在第五个项目上花费 2 个时间单位,在第四个项目上花费 2 个时间单位;程序员 3 在第四个项目上花费 4 个时间单位。因此两人的总工作时间都是 4。

第四个情形中,程序员 1 和 3 分别在第一个和第三个项目上工作 18/718/7 个时间单位。程序员 2 在前三个项目上分别工作 5/7,1,6/75/7,1,6/7 个时间单位,总计也是 18/718/7。

第五个情形中,为完成最后两个项目,程序员 1 和 5 中至少一人的工作时间必须达到 28/328/3。存在使每个人的总工作时间都不超过 28/328/3 的安排。