{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:30.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/9163a97ff442ea7c56a8f5997f200590?v\u003d1715804634\" alt\u003d\"/problems/cats/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003e\n \u003cp\u003eYour crazy aunt has asked you to watch her cats while she’s\n attending a seminar about making cat hats out of cat fur. Your\n aunt owns a great number of cats – all toms – and, due to the\n complex social structure of cats, every cat has a specific but\n different amount of hate reserved for every other cat.\u003c/p\u003e\n \u003cp\u003eOver the years, the cats have been spoiled to the point that\n they demand (at the least) \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e milliliter of milk at tea time.\n Your task is to feed the cats the aforementioned milk, in order\n to dull their primal instincts and prevent an all-out cat\n war.\u003c/p\u003e\n \u003cp\u003eThe task is complicated by three things:\u003c/p\u003e\n \u003col class\u003d\"enumerate\"\u003e\n \u003cli\u003e\n \u003cp\u003eYour aunt has a limited amount of milk stored in the\n fridge.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eFor each pair of cats, there is a distance they have to\n be kept from each other to avoid infighting.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe excessive amount of meowing has driven you to drink\n large amounts of hard liquor, and now you can’t move\n liquids without constant spilling. You will spill\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e milliliter of the\n milk you carry for every meter you walk.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ol\u003e\n \u003cp\u003eGiven an amount of milk, and a set of cats – each pair of\n cats being a given distance apart from each other – determine\n if it’s possible to feed every cat at least \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e milliliter of milk. Every cat has\n a cat bowl that can hold an arbitrary amount of milk. For every\n meter you walk, you will definitely spill \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e milliliter of milk (instantly\n spoiling it), but instead of carrying all the milk at once, you\n may serve a cat more milk than needed and pick it up when\n backtracking (the cat will not drink the excess milk before\n you’re finished walking). The cats will never move, but they\n will eye each other with intense hate.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line of the input consists of a single integer\n \u003cspan class\u003d\"tex2jax_process\"\u003e$T$\u003c/span\u003e, the number of test\n cases.\u003cbr\u003e\n Each of the following \u003cspan class\u003d\"tex2jax_process\"\u003e$T$\u003c/span\u003e\n cases begins with a line containing two positive integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$C$\u003c/span\u003e, separated by a space, denoting\n the amount of milk in the fridge in milliliters and the number\n of cats, respectively.\u003cbr\u003e\n This is followed by \u003cspan class\u003d\"tex2jax_process\"\u003e$\\frac{C\n \\cdot (C-1)}{2}$\u003c/span\u003e (combinations of cats) lines containing\n three positive integers \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$D_{i,j}$\u003c/span\u003e, separated by single spaces,\n describing the distance between the cat with index \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e and the cat with index\n \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e in meters. Cats are\n numbered from \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e up to\n and including \u003cspan class\u003d\"tex2jax_process\"\u003e$C-1$\u003c/span\u003e, and\n each pair of cats will be listed exactly once. You may assume\n that the fridge is placed at the very same location as cat\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e.\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq T \\leq\n 20$\u003c/span\u003e\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq M \\leq 20\\,\n 000$\u003c/span\u003e\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq C \\leq 2\\,\n 000$\u003c/span\u003e\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq D_{i,j} \\leq 3\\,\n 000$\u003c/span\u003e\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eCats co-exist in dimensions far greater than our three,\n so you can assume that every pair of cats is correctly\n separated by \u003cem\u003eexactly\u003c/em\u003e the given distance.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput \u003ctt class\u003d\"ttfamily\"\u003eyes\u003c/tt\u003e if it’s possible to\n serve every cat at least \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e milliliter of milk. Output\n \u003ctt class\u003d\"ttfamily\"\u003eno\u003c/tt\u003e if it’s not.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e1\n20 5\n0 1 4\n0 2 3\n0 3 10\n0 4 15\n1 2 7\n1 3 3\n1 4 5\n2 3 4\n2 4 3\n3 4 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eyes\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}