/ AOCode / 题库 /

Tokens re-collection

Tokens re-collection

P1042 Tokens re-collection

Problem Background

AppOfficer didn't run out of the maze. All his tokens were snatched by Cui2010. Now he wants to
get all his tokens back. Unfortunately, he can't.

Problem Statement

Now AppOfficer is trapped in a hole. He's at point 11. The exit is at point nn. His mm tokens are placed in some parts of the hole. There are kk edges. For each edge, there're three integers xx yy tt, means that he can go directly from point xx to point yy in tt minutes. But he can't go from yy to xx! AppOfficer not only wants to get his tokens back, but also wants to escape the hole ASAP. So if he gets aa tokens back, and he reaches point nn in bb minutes, he wants to minimize (50a)×b(50-a) \times b. Please tell him the product. If he cannot reach point n, print Czy you don't have force morality! Rat tail juice!.

Input

The first line includes three integers nn, mm, kk.
The second line includes mm integers, they mean where AppOfficer's tokens are.
Next kk lines, every line includes three integers xx, yy, tt, describing an edge.

Output

One integer, the product. Or Czy you don't have force morality! Rat tail juice!

Constraints

  • 1n105 1 \le n \le 10^5
  • 1m50 1 \le m \le 50
  • 1kmin{n×(n+1)2,5×105} 1 \le k \le \displaystyle \min \left\{\frac {n \times (n+1)} {2}, 5 \times 10^5 \right\}
  • 1x<yn 1 \le x < y \le n
  • 1t104 1 \le t \le 10^4

Samples

Input 1

3 1 3
2
1 2 1
2 3 3
1 3 3

Output 1

150

There're two kinds of ways to reach point nn.

  • 1231\Rightarrow2\Rightarrow3 time: 44 , tokens: 11. So the product is (501)×4=196(50-1) \times 4 = 196
  • 131\Rightarrow3 time: 33 , tokens: 00. So the product is (500)×3=150(50-0) \times 3 = 150

Input 2

3 2 1
2 3
1 2 1

Output 2

Czy you don't have force morality! Rat tail juice!

It's obvious that AppOfficer cannot escape the hole.

信息

ID
1042
难度
1150
分类
(无)
标签
递交数
62
已通过
4
通过率
6%
被复制
2
上传者

相关

在下列比赛中:

AOCode Round #4