HUSTOJ

Description

经过辛勤的工作，墓道终于清理干净，小可可随考古队进入了墓室，在墓室的入口处，小可可发现了一张古代的壁画，这幅壁画清楚的描绘了古墓的平面布局，原来这个古墓有N个墓室，M个双向墓道，每条墓道连接两个不同的墓室,两个墓室之间可能有多条墓道相连，且每条墓道上都可能会有机关。入口墓室标号为1号，主墓室标号为N号，壁画上同时标明了整个古墓内总共有K种机关，并且知道每种机关在每条道路上出现的概率，并且告知了这些机关都可以用一些工具破坏掉，工具也共有K种，第i(1≤i≤K)种宝剑能且只能破坏第i种机关。每个墓室里都可能有一些这样的工具，包括１号墓室（假设墓室里有的工具数量都为无限多，想拿多少就拿多少）。如果小可可在某条墓道上遇到某种机关，他又没有能破坏这种机关的专用工具，那他将可能会受伤，不能到达N号墓室了。现在小可可一种工具也没有没有，但他有足够的力气来带任意多的工具，他想知道的是能成功到达N号墓室（即主墓室）的最大概率是多少。

Input

第一行有三个正整数N,M,K分别用一个空格分开，意义如上所述。接下来M行,每行有P+2个正整数，分别是U,V,p_1,p₂,…,p_K,分别用一个空格分开，表示有一条墓道连接U,V(U≠V)两个墓室，这条道路上第i(1≤i≤K)种机关出现概率为p_i%,保证0≤p_i≤100，且p₁+p₂+…+p_K≤100.
接下来N行，按顺序分别描述1~N号墓室中保有工具的情况，每行K个整数t₁,t₂,…,t_K，分别用一个空格隔开,其中t_i(1≤i≤K)为1表示该墓室内有能破坏第i种机关的工具，否则t_i必为0表示该墓室内没有能破坏第i种机关的工具。

Output

只输出一个实数表示小可可能成功到达N号墓室（即主墓室）的最大概率，四舍五入到小数点后3位.

Sample Input Copy



5 6 3


1 2 10 0 0


1 3 0 20 0


1 4 0 0 30


2 5 90 10 0


3 5 10 90 0


4 5 0 10 90


0 0 0


1 0 0


0 1 0


0 0 1


1 1 1

Sample Output Copy



0.810

HINT

提示：
对40%的数据，N≤10,M≤100,P≤4
对100%的数据，N≤500,M≤1000,P≤10.

Source/Category

AHOI初中 2010 level5