{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"The **ACM (Advanced Car Management) Rent a Car** company is very famous now-a-days because of their quality and service. Gaining popularity is not that easy as there are many competitors around. Each day they have a large number of car requests. Once a car is used for a day, if they want to use it later, they should send it for servicing. Actually it was their key theme for business and that\u0026#8217;s why they are so popular.\n\nThere are **C** motor companies in town, where the **k\u003csup\u003eth\u003c/sup\u003e** company has **c\u003csub\u003ek\u003c/sub\u003e** cars in their showroom and price of a car of this company is **p\u003csub\u003ek\u003c/sub\u003e**. There are **R** car service-centers in town, the **i\u003csup\u003eth\u003c/sup\u003e** center takes **d\u003csub\u003ei\u003c/sub\u003e** days and costs **s\u003csub\u003ei\u003c/sub\u003e** per car service. Service centers can service huge number of cars at the same time.\n\nNow, ACM company has the request sheet for next **N** days, where in **j\u003csup\u003eth\u003c/sup\u003e** day, **r\u003csub\u003ej\u003c/sub\u003e** cars are needed. They want to fulfill all the requirements with minimized cost. Initially, ACM has empty garage. But their garage is huge and can store any number of cars.\n"}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 100)**, denoting the number of test cases.\n\nEach case starts with three integers **N, C, R (1 \u0026le; N, C, R \u0026le; 50)**. The next line contains **N** integers where the **j\u003csup\u003eth\u003c/sup\u003e** integer denotes **r\u003csub\u003ej\u003c/sub\u003e (0 \u0026le; r\u003csub\u003ej\u003c/sub\u003e \u0026le; 100)**. The next line contains **2C** integers where the **k\u003csup\u003eth\u003c/sup\u003e** integer-pair denotes **c\u003csub\u003ek\u003c/sub\u003e** and **p\u003csub\u003ek\u003c/sub\u003e** **(1 \u0026le; c\u003csub\u003ek\u003c/sub\u003e, p\u003csub\u003ek\u003c/sub\u003e \u0026le; 100)**. The next line contains **2R** integers where the **i\u003csup\u003eth\u003c/sup\u003e** integer-pair denotes **d\u003csub\u003ei\u003c/sub\u003e** and **s\u003csub\u003ei\u003c/sub\u003e** **(1 \u0026le; d\u003csub\u003ei\u003c/sub\u003e, s\u003csub\u003ei\u003c/sub\u003e \u0026le; 100)**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the minimized cost to fulfill all the requests. If it\u0027s impossible to do so, print `impossible`."}},{"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\n3 2 1\n10 20 30\n40 90 15 100\n1 5\n3 2 1\n10 20 30\n40 90 15 100\n2 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 4650\nCase 2: impossible\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"For case 1, 50 cars will be bought, 40 from company 1 (costs 40\\*90\u003d3600) and 10 from company 2 (costs 10\\*100\u003d1000). On day 1, 10 cars will be sent and then they will be sent to the service center (costs 10\\*5\u003d50). The cars will be received on day 3. On day 2, 20 cars will be sent. And on day 3, 20 unused cars will be sent along with the 10 cars (serviced). So, overall cost is 3600+1000+50 \u003d 4650."}}]}