{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"题意:","value":{"format":"HTML","content":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;} \u003c/style\u003e \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027]]}\n });\n \u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n \u003c/script\u003e\n\u003cp\u003eStatements: \u003ca href\u003d\"https://codeforces.com/gym/101873/attachments\"\u003ehttps://codeforces.com/gym/101873\n/attachments\u003c/a\u003e\u003c/p\u003e\n\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;这是七月的又一个阳光灿烂的日子,你决定和你的小女儿一起度过快乐的一天。因为她真的很喜欢隔壁镇上的仙女公园,所以你决定到那儿去玩一天。\n\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; 你妻子同意开车送你去公园接你。她非常准时,所以她确切地告诉你她什么时候会到公园的前门来接你,而你必须恰好在那个时间到那里。因为你显然也不想在外面等,这样会让你的小女儿伤心——她本可以在公园里多待些时间。\n\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;现在你必须考虑游玩计划。你知道你什么时候到达,什么时候离开。公园由若干游玩设施组成,两两之间由人行道相连。进入公园是免费的,但你每次使用在公园里的某项设施,都必须付一次相应费用。你已经知道玩每一项游玩设施各自需要多长时间、花多少钱。\n\u003cbr\u003e \u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;当你穿过公园时,你显然不能在沿着公园走的时候跳过游乐设施(即使乔伊已经玩过,即达到该游乐设施时,至少得玩一次),否则乔伊会很伤心。因为乔非常喜欢公园,她很乐意玩同一个项目不止一次。在两个游乐项目之间行走需要一定的时间。\n\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;因为你是一个有计划的家长,所以当你在公园的时候,你要尽量少花钱。你能计算至少要花多少钱吗?"}},{"title":"输入:","value":{"format":"HTML","content":"一行,一个整数 x(1≤x≤1e3) 代表你们在公园玩的确切时间。\n\u003cbr\u003e一行,三个整数 n,m,w(1≤n,m,w≤1e3),代表有 n 个娱乐设施, 之间有 m 条人行道连接,走人行道需要花费 w 分钟。\n\u003cbr\u003em 行,每行 a,b 代表设施 a,b 之间有一条人行道。\n\u003cbr\u003en 行,每行 t,p 代表该项游乐设施花费 t 分钟,p 元。(1\u003c\u003dt,p \u003c\u003d 1e6)\n\u003cbr\u003e你从设施 1 出发,最后必须回到设施 1。\n\u003cbr\u003e"}},{"title":"输出:","value":{"format":"HTML","content":"如果能恰好待够 x 分钟,则输出最小花费,否则输出\u0026nbsp; “ It is a trap.”"}},{"title":"样例1:","value":{"format":"HTML","content":"Sample Input 1\n\u003cbr\u003e4\n\u003cbr\u003e4 4 1\n\u003cbr\u003e1 2\n\u003cbr\u003e2 3\n\u003cbr\u003e3 4\n\u003cbr\u003e4 1\n\u003cbr\u003e1 2\n\u003cbr\u003e2 1\n\u003cbr\u003e5 4\n\u003cbr\u003e3 3\n\u003cbr\u003eSample Output 1\n\u003cbr\u003e8"}},{"title":"样例2:","value":{"format":"HTML","content":"Sample Input 2\n\u003cbr\u003e6\n\u003cbr\u003e4 4 1\n\u003cbr\u003e1 2\n\u003cbr\u003e2 3\n\u003cbr\u003e3 4\n\u003cbr\u003e4 1\n\u003cbr\u003e1 2\n\u003cbr\u003e2 1\n\u003cbr\u003e5 4\n\u003cbr\u003e3 3\n\u003cbr\u003eSample Output 2\n\u003cbr\u003e5"}}]}