{"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 \u003cp\u003eThere are \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e files to\n be printed using \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e\n identical printers. The files are numbered from \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e. The printers are numbered from\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e. Assuming each page takes one unit\n of time to print, for each file \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e, we have the following\n information:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe number of pages it contains, \u003cspan class\u003d\"tex2jax_process\"\u003e${p}_{i}$\u003c/span\u003e (i.e. the time it takes\n to print file \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e);\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eReady time \u003cspan class\u003d\"tex2jax_process\"\u003e${r}_{i}$\u003c/span\u003e (the printing of the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e cannot be started\n before time \u003cspan class\u003d\"tex2jax_process\"\u003e${r}_{i}$\u003c/span\u003e);\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eFinish time \u003cspan class\u003d\"tex2jax_process\"\u003e${d}_{i}$\u003c/span\u003e (the printing for file\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e has to be\n completed no later than time \u003cspan class\u003d\"tex2jax_process\"\u003e${d}_{i}$\u003c/span\u003e).\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eWe can assume that \u003cspan class\u003d\"tex2jax_process\"\u003e${d}_{i} -\n {r}_{i} \\geq {p}_{i}, 1 \\le i \\le n$\u003c/span\u003e. The printing\n process of a file can be interrupted between pages. In other\n words, while printing file \u003cspan class\u003d\"tex2jax_process\"\u003e$f$\u003c/span\u003e, the printer can interrupt this\n job and move to print a different file. The printing process of\n file \u003cspan class\u003d\"tex2jax_process\"\u003e$f$\u003c/span\u003e can be resumed on\n any available printer afterwards. We can assume that:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe time it takes to move the printing of a file from\n one printer to another printer is negligible.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe starting time for printing the files is \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eA schedule of printing \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e files using \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e printers has to satisfy the\n following requirements:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe printing of each file \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e cannot be started before the\n ready time \u003cspan class\u003d\"tex2jax_process\"\u003e${r}_{j}$\u003c/span\u003e;\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe printing of each file \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e has to be completed no later\n than the finish time \u003cspan class\u003d\"tex2jax_process\"\u003e${d}_{j}$\u003c/span\u003e;\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eAt any one time, the printing of file \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e can be processed by at most\n one printer and the total amount of printing time of file\n \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e, i.e. its number\n of pages, is \u003cspan class\u003d\"tex2jax_process\"\u003e${p}_{j}$\u003c/span\u003e;\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eAt any one time, each printer can only process at most\n one page of one file.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eYour task is to find if there exists a schedule to print\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e files using\n \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e printers satisfying\n the requirements.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input consists of several datasets. The first line of\n the input contains the number of datasets which is a positive\n number and is not greater than \u003cspan class\u003d\"tex2jax_process\"\u003e$25$\u003c/span\u003e. The following lines describe the\n datasets.\u003c/p\u003e\n \u003cp\u003eEach dataset is described by the following lines:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe first line contains two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n, m$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 \\leq n, m \\leq 200)$\u003c/span\u003e;\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe \u003cspan class\u003d\"tex2jax_process\"\u003e${i}^\\textrm\n {th}$\u003c/span\u003e line in the following \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e line contains three positive\n integers \u003cspan class\u003d\"tex2jax_process\"\u003e${p}_{i}$\u003c/span\u003e,\n \u003cspan class\u003d\"tex2jax_process\"\u003e${r}_{i}$\u003c/span\u003e, and\n \u003cspan class\u003d\"tex2jax_process\"\u003e${d}_{i}$\u003c/span\u003e, where\n \u003cspan class\u003d\"tex2jax_process\"\u003e${p}_{i}, {r}_{i}, {d}_{i}\n \\leq 30\\, 000$\u003c/span\u003e for \u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le i \\le n$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eFor each dataset, output \u003ci class\u003d\"itshape\"\u003eYES\u003c/i\u003e if a\n valid schedule exists, \u003ci class\u003d\"itshape\"\u003eNO\u003c/i\u003e otherwise. In\n case the solution does exist, describe an \u003cb class\u003d\"bfseries\"\u003earbitrary\u003c/b\u003e valid schedule as below:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe description contains \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e blocks of lines, each provides\n instruction for printing a file.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe first line of the \u003cspan class\u003d\"tex2jax_process\"\u003e${i}^\\textrm {th}$\u003c/span\u003e block contains\n an integer \u003cspan class\u003d\"tex2jax_process\"\u003e${\\zeta\n }_{i}$\u003c/span\u003e - the number of \u003ci class\u003d\"itshape\"\u003eperiods\u003c/i\u003e the \u003cspan class\u003d\"tex2jax_process\"\u003e${i}^\\textrm {th}$\u003c/span\u003e file gets\n printed.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eEach of the rest \u003cspan class\u003d\"tex2jax_process\"\u003e${\\zeta\n }_{i}$\u003c/span\u003e lines of this block contains three integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x, y, z$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$({d}_{i} \\leq x \u0026lt; y \\leq {r}_{i}, 1\n \\leq z \\leq m)$\u003c/span\u003e, meaning that the \u003cspan class\u003d\"tex2jax_process\"\u003e${i}^\\textrm {th}$\u003c/span\u003e file is\n \u003cb class\u003d\"bfseries\"\u003econstantly\u003c/b\u003e printed from time\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e to time\n \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e by the\n \u003cspan class\u003d\"tex2jax_process\"\u003e${z}^\\textrm {th}$\u003c/span\u003e\n printer.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eWrite an extra blank line after every test case.\u003c/p\u003e\n \u003ch2\u003eNotes\u003c/h2\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eNo two periods corresponding to one file can\n overlap.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eNo two periods assigned to one printer (even from two\n different files) can be overlap.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eYour program must not provide any \u003cb class\u003d\"bfseries\"\u003elarger than \u003cspan class\u003d\"tex2jax_process\"\u003e$10$\u003c/span\u003eMB\u003c/b\u003e output for every single\n input file.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003ch2\u003eClarification for Sample Output\u003c/h2\u003e\n \u003cp\u003eValid solutions exist for the former dataset, but do not for\n the latter one. As stated in the sample output:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe first file is printed by the first printer from time\n \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e, by the second printer from\n time \u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e to\n \u003cspan class\u003d\"tex2jax_process\"\u003e$7$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe fourth file is firstly printed by the first printer\n in one second, immediately switched to the second one for\n another second. From time \u003cspan class\u003d\"tex2jax_process\"\u003e$7$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$8$\u003c/span\u003e, it gets printed by the first\n printer and then from \u003cspan class\u003d\"tex2jax_process\"\u003e$8$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$10$\u003c/span\u003e by the second printer.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\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\u003e2\n4 2\n4 2 7\n3 3 8\n3 4 7\n5 1 10\n4 1\n4 2 7\n3 3 8\n3 4 7\n5 1 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\n2\n2 4 1\n5 7 2\n2\n7 8 1\n3 5 2\n1\n4 7 1\n4\n1 2 1\n8 10 1\n2 3 2\n7 8 2\n\nNO\n\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}