给定K种化学物质和N种反应类型，每个反应都有一些反应物质和生成物质，且反应需要一定的时间。假设每次反应后的若干生成物都可以完全分离。即每次反应的生成物，可以立即用于其他反应的生成物。每种物质的数量都是无限的。 请编写一个程序，给出一些已有的物质，求由此得到一种指定物质至少要多少时间？

第一行有4个整数，分别为K（3<=K<=250), N(3<=N<=500),已有物质的数量M（1<=M

输出

仅一行一个整数，表示生成指定的物质需要的最短的时间。如果无法生成指定物质，则输出-1。

样例输入

4 3 1 4
8
1 1
1 4
3
1 1
2 2 3
2
2 1 3
1 4

样例输出

5

【样例解释】

先做第2个，再做第3个，得到目标4，花费时间为5

来源/分类

 

[提交] [状态]