{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eBrickgao, who profited from your accurate calculating last year, made a great deal of money by moving bricks. Now he became ``gay shy fool\u0027\u0027 again and recently he bought an iphone and was deeply addicted into a cellphone game called Ingress. Now he is faced with a problem so he turns to you for help again. We make some slight modifications based on the original rules, so please draw attention to the details below.\u003cbr\u003e\u003cbr\u003eThere are $N$ portals (indexed from 1 to $N$) around Brickgao\u0027s home, and he can get some substances called XM by hacking the portals. It\u0027s known that for each portal $i$, he can get $A_i$ XM during the first hack, and after each hack, the amount of XM he will get during the next hack will decrease by $B_i$. If the amount of XM he can get is less than or equal to zero, Brickgao can\u0027t get XM from that portal anymore. For the $i$-th portal, if $A_i \u003d 10, B_i \u003d 2$ and he hacks 3 times, he will get 10, 8, 6 XM during each hack.\u003cbr\u003e\u003cbr\u003eThere are $M$ bidirectional roads between some pairs of portals and between Brickgao\u0027s home and some portals. Now he is eager to start his Ingress journey from home and finally return home, but due to the extremely hot weather, Brickgao will feel sick when you hack more than $K$ times or the distance he covers is more than $L$. So how much XM he can get at most during this journey?\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains a single integer $T(T\\leq 20)$, indicating the number of test cases.\u003cbr\u003e\u003cbr\u003eThe first line of each case are four integers $N(1\\leq N \\leq 16), M(0 \\leq M \\leq \\frac{N(N+1)}{2}), K(1 \\leq K \\leq 50)$ and $L(2 \\leq L \\leq 2000)$.\u003cbr\u003eThe second line of each case contains $N$ non-negative integers where the $i$-th denotes $A_i(A_i \\leq 500)$.\u003cbr\u003eThe third line of each case contains $N$ non-negative integers where the $i$-th denotes $B_i(B_i \\leq 50)$.\u003cbr\u003eEach of next $M$ line contains 3 non-negative integers $u, v ( 0\\leq u,v\\leq n)$ and $c (0\\leq c\\leq 1000)$ , denotes that there is a road with the length of $c$ between the $u$-th and the $v$-th portal. If $u$ or $v$ equals to 0, it means Brickgao\u0027s home.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output the case number first, then the amount of maximum XM Brickgao can get.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n1 1 3 2\r\n5\r\n3\r\n0 1 1\r\n3 6 3 5\r\n10 7 5\r\n2 3 1\r\n0 1 3\r\n0 2 1\r\n0 3 1\r\n1 2 2\r\n2 3 3\r\n1 3 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 7\r\nCase 2: 16\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}