{"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:35.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/2cc32d1232c75f2d5b3f4088fa46767a?v\u003d1716038213\" alt\u003d\"/problems/jupiter/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eAlthough we imagine interplanetary probes to be very\n sophisticated pieces of technology, their information systems\n are quite archaic. You might assume that they have a certain\n amount of contiguous main memory and can store their data\n wherever is convenient, but unfortunately that is not the case.\n The probe’s main memory is organised in a number of FIFO\n (first-in-first-out) queues. In such a queue, data has to be\n taken out of the queue in the same order as it has been added\n to it.\u003c/p\u003e\n\n \u003cp\u003eA probe has multiple sensors and each sensor is linked to\n one of the queues. Whenever a sensor finishes recording, it\n appends the generated data to its queue. A sensor can write\n data to the queue only if the queue has enough space left to\n take all the data; if not, the data is lost.\u003c/p\u003e\n\n \u003cp\u003eIn order to transfer data from the probe to Earth (in a\n process called \u003cem\u003edownlinking\u003c/em\u003e), the path between the\n satellite and Earth must not be blocked by anything\n (e.g.\u0026nbsp;a planet like Jupiter) and the antenna must be\n correctly positioned. During each downlink opportunity, data\n can be taken from multiple queues and transmitted back to\n Earth. The total amount of data that can be transmitted during\n a downlink opportunity depends on the length of the downlink\n opportunity and distance to Earth. Sensors do not collect data\n during downlink opportunities, since all electricity available\n is devoted to the transmitter.\u003c/p\u003e\n\n \u003cp\u003eThe most important thing for scientists is not to lose any\n data recorded by sensors. In particular, all queues have to be\n empty after the last downlink opportunity. The scientists have\n asked you to write a program to determine whether all data can\n be transferred to Earth in a given time frame.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eone line containing three positive integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n,q,s$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\\leq n,q \\leq 30$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq s \\leq 100$\u003c/span\u003e), the number\n of downlink windows, FIFO queues, and sensors,\n respectively.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eone line with \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e\n integers \u003cspan class\u003d\"tex2jax_process\"\u003e$q_1 \\ldots q_\n s$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq q_ i \\leq\n q$\u003c/span\u003e for each \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e), determining for each sensor\n the queue it feeds its data into.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eone line with \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e\n integers \u003cspan class\u003d\"tex2jax_process\"\u003e$c_1 \\ldots c_\n q$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq c_ i \\leq\n 10^6$\u003c/span\u003e for each \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e), determining for each queue\n the size of the queue in megabytes.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines, each\n describing one downlink window. Each contains \u003cspan class\u003d\"tex2jax_process\"\u003e$s + 1$\u003c/span\u003e non-negative integers.\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe first integer \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq d \\leq 10^6$\u003c/span\u003e) states\n the number of megabytes that can be transferred to\n earth during the window.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eThe following \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e numbers \u003cspan class\u003d\"tex2jax_process\"\u003e$a_1 \\ldots a_ s$\u003c/span\u003e\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq a_ i \\leq\n 10^6$\u003c/span\u003e for each \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e) describing the amount of\n data (in megabytes) generated by each of the sensors\n after the last but before this downlink window.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eThere will never be new data during a downlink window.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput “\u003ctt class\u003d\"ttfamily\"\u003epossible\u003c/tt\u003e” if it is\n possible to transfer all data to Earth, and “\u003ctt class\u003d\"ttfamily\"\u003eimpossible\u003c/tt\u003e” otherwise.\u003c/p\u003e\n\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 2 2\n1 2\n3 3\n5 2 2\n5 2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003epossible\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\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 2 2\n1 2\n3 3\n1 2 2\n5 2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eimpossible\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}