Problem H: 技术员BangFu

上一题 正确率: $13.33\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $15$ 正确数量 $2$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 图论 动态规划

Description

BangFu是通讯公司的技术员。某个星期一刚去上班，BOSS就给了他一个任务，去非洲检查通讯设备！这让他感觉非常不爽，他非常讨厌这项工作。更让他感觉不爽的是去的路费还得自己掏！但是最最最让他感觉不爽的是，如果完成任务后在工作日回来，万恶的BOSS肯定还会给他新的任务！连休息的机会都没有！这实在是太糟糕了。

BangFu多么希望完成任务后能在周六或者周末回来。如果在这个基础上能够省点路费，那就更好了。作为BangFu的好朋友，你必须帮助他。

假设BangFu一共要去N-1个地方检查设备，分别编号为1 到N-1。起始地点在公司，编号为0，完成检查后他要返回公司。BangFu在每个地方要花1天时间检查，他不会去已经检查过的地方，检查完所有设备前也不会返回公司。而且他不愿意把时间浪费在非洲，就是说完成检查他立马会去另外一个地方。现在告诉你这N个地点之间路线情况，帮他选择一条最佳路线吧。

Input

有多组测试数据，每组数据第一行为两个整数N和M。
N表示一共有N个地点，M表示这N的地点之间有M条路线。

接下来有M行，每行4个整数x、y、p、t。
表示从x到y有一条路线，走这条路线要花p块钱和t天时间。
所有路线都是单向的，两个地方可能有多条路线。(1<N<=10,0<=M<=200,x!=y)。

Output

每组数据输出占一行。
如果BangFu不能完成任务，输出”It’s not my thing!”； 
如果BangFu可以完成任务，但是不能周六或者周日回来，输出”Oh, My god!”；
如果BangFu可以完成任务，并且能够周六或者周日回来，输出他最少要花销的车费。

Sample Input复制

2 2
0 1 1 3
1 0 1 1
2 2
0 1 1 2
1 0 1 1
3 4
0 1 2 3
1 0 1 4
0 2 2 5
2 0 1 7

Sample Output复制

2
Oh, My god!
It's not my thing!

提示

第一组数据中，BangFu去地点1检查设备。去的路上花了3天，维修花了1天，回来路上花了1天，一共花了5天。去的时候是星期一，所以正好星期六回来。