题目描述
Lazy boy has gone home during his vacations. As it is the season of Holi, his mother expects him to
do some of her work so that she can relax a little bit. However, since lazy boy is lazy, he wants to do
as less work as possible, giving him more time to sleep, as lazy boy loves to sleep. However, he also
knows that he needs to do a minimum amount of work, otherwise he will be scolded by his father
for being too lazy. There are n distinct tasks that her mother asks him to do, and each task has an associated
amount of work with it. Lazy boy knows how much amount of work he needs to do to avoid being
scolded by his father. He wants to do this much amount of work by doing the least number of tasks.
Also, he never does more than two distinct tasks. Lazy boy wants to know what is the minimum
number of tasks he should do so that the total amount of work done by him is equal to the required
amount of work to avoid being scolded. Lazy boy makes q such queries to you, you need to give an
answer for every query.
You will be given an array a, of n elements, giving the amount of work associated with each of the n
tasks, and a number k, meaning the lazy boy never does more than k tasks in total. After that there will be q
queries. For each query, which contains a single number, you need to tell what is the minimum
number of tasks he should do to achieve the amount of work given in the query. If it is not possible
to do so, output “:(” (without quotes).
Note : Lazy boy does at most two of the distinct tasks assigned by his mother, and he does not do more than k
tasks in total. He can repeat a task many times, as long as he does less than or equal to k tasks.
Input :
First line contains two integers n (number of tasks) and k (maximum number of tasks lazy boy
does).
Next line contains n space-separated integers, the array a, giving the amount of work associated
with each task.
Next line contains q, the number of queries.
Each query contains an integer x (the required amount of work to be done).
Output :
For each query, output the minimum number of tasks he should do so that total amount of work
done is equal to x. If it is not possible to do so, print “:(” (without quotes).
Constraints :
n ≤ 5000
k ≤ 20
ai ≤ 10^7
q ≤ 20
x ≤ 2*10^8
Problem setter : Sahil Prakash
SAMPLE INPUT
5 4
1 2 11 12 14
3
1
4
9
SAMPLE OUTPUT
1
2
:(
Explanation
Explaination (for 3 rd query) :
Since it is not possible to get total amount of work done equal to 9 by
doing only two of the available tasks, not doing more than 4 tasks in total, the ouput is “:(”.
输入格式
见题面
输出格式
见题面
样例输入
1261 17
5042863 599431 4966467 9322841 4738138 3510896 674280 3220561 6813451 1754294 9972137 7558640 3663277 5165540 2764480 2065705 6974523 5704875 6109875 4519246 8781325 294525 6687068 8019470 2112271 5246438 829561 3446011 7211059 4892174 1947037 2253922 5491604 9429856 4093114 229741 5457103 4767393 3450301 2270553 6521687 5938789 2345544 2701315 1104328 5110024 4767019 595203 3331250 876893 5114448 4628926 3687770 4317867 2648395 5800040 2080657 5994308 9246050 1808067 886481 3709439 4061988 8894436 3139294 671454 9124176 8596396 5438846 5090829 3383301 4476884 3545969 8245196 7178199 4650297 5871571 4461569 5245499 9202820 5338462 2876298 6348097 9026231 7194165 8996492 7342622 1791173 4990799 6588672 3599239 8393631 298110 177579 7288066 3437403 849032 6412241 4550150 8804229 4019421 449802 5797465 7565390 8694998 5492015 4732038 4566568 9953583 9977536 6285740 7808396 2853833 2633836 6834626 2564349 4146679 4177248 6871873 9137477 3282271 2987464 7531107 3580380 3165042 4819172 9534134 6530425 3747765 6600635 5334653 283537 7050437 3648469 7848926 5745434 9140483 5097315 2828353 1610418 5074850 9114092 9418813 445035 4264280 8769791 5525735 8410958 2947038 2397608 64787 6229308 5385071 7595893 2326039 1066464 4931417 4376524 7596888 1195533 977158 5447892 1479069 8027594 1612713 1844347 6289379 753195 6941661 9117732 4879964 4532863 748175 4298777 7494249 5012454 3068567 3019983 5939764 8531956 7933942 6004550 7277615 5835364 3600442 2120005 6901827 1048210 6496528 7015066 4760094 9990037 4979310 6239163 8017631 6592022 599861 6823361 9861568 57873 8457444 4741532 7107087 1721971 1556660 4601335 9250776 4625226 137670 5190539 5673533 8071611 1195088 2951147 6423327 7311882 5071151 5841505 8360091 4084030 2856571 3120185 4074066 7835880 1875699 4608048 6944253 4991911 1431409 6805820 7566135 2405204 4063703 4673222 4127174 5620362 9274556 3377950 2761939 1928577 8568488 8435471 2516540 2279928 3902969 8939866 9591809 1490471 4781370 7951899 5574500 7637940 3588435 9648566 7990171 7980485 4256613 7450775 5488747 5688021 6772947 3054882 609577 836649 7728103 4736750 8973363 9519010 631051 1735301 1447587 1715891 2687124 3964126 3995818 9106444 5420343 3587626 596915 201712 4055876 6171414 356004 160663 5819979 862526 657499 76592 8313301 6146246 8280964 5086247 9201127 1406892 8439247 9445581 8659994 7412609 1480942 9291044 1664262 5444880 1006934 4351385 9409005 7519103 3457828 7345699 1106728 6571094 7547411 5162604 2742508 419766 7839618 8562486 1282291 8497116 1155429 9595591 4643361 1952745 7198189 6360839 3359636 5637436 5806419 2019629 5566396 9803713 3827025 7230657 5248592 7350310 4098393 7173949 4869413 7556221 4519647 5976140 4127314 2067057 3655095 9386173 5003174 4011064 465011 6285465 2508180 4136791 8397407 9667892 6089535 5595596 6028731 1965523 3749383 4351501 6501503 9315778 4155213 2844879 9062787 9403805 195189 3161179 6577753 5064601 717399 1097399 3557092 7361065 5680808 7212187 9263589 683981 1223250 9728599 9485797 6247781 3865390 7883204 5915673 2471276 5995151 4460755 4436798 2260885 8812255 3454653 1576662 5483820 6299531 639448 4887624 6494719 6316979 3981728 4075671 7034377 7595478 7632763 6911793 3276285 7361301 6175382 6476618 1100902 8420332 5962414 7348683 2285721 6361969 5780707 4756997 2357119 241461 1710146 4618003 1570067 7681150 8711017 7053886 3980681 1866816 4457861 2991751 8183794 8439588 7067422 7734523 6035066 7216536 7162667 1827702 4577836 5854400 8304319 8195089 4274732 6783085 5543771 6560452 3145053 1324477 3833800 5502172 4082289 5543946 2636526 5652356 3225095 3863894 5222593 9722127 5730710 9680454 2713878 6430855 8120041 2297651 6681729 6671458 2030538 3844396 8499160 9124725 9698795 9319830 7319813 3973526 8619266 5379936 3050330 1764319 9220764 6884129 9782842 3303053 4944426 2419367 1471760 8169521 8799613 6694352 407999 4530322 6374805 5638228 3477528 7011198 452230 159257 3682655 2482767 4003652 4698166 1607491 6218798 6534348 8927304 2708676 5153613 4307239 5759005 6917931 3528002 5159485 6700772 9347406 2620263 1636491 819165 3306135 436103 7513517 3714133 7482776 6404673 9352361 3476655 3415870 9804590 3635911 7098525 2287357 155914 4313042 6411199 6374712 847389 7854854 9083387 6001002 4678444 7358743 5435284 722798 5034579 4652408 70203 7654841 8805250 3405720 960975 1757704 919236 7191460 1756831 7323908 6543820 5233485 3256130 8864761 8869396 2871006 3668469 9025309 7184047 79668 5400020 547788 7934521 6999758 9065141 5129317 6874852 4500424 5852114 4425783 9152831 5922316 2080623 7958080 9328035 5557950 2232135 2763622 2749409 3988965 2603882 1809580 9222450 5860011 674340 8091845 8731016 4342809 9633505 8431414 6938828 5033525 8979201 7389700 4549634 8044341 2519016 3940838 2544765 8371129 8366620 4213947 6809797 2963594 4688379 6137831 1037895 6920513 1417805 6303655 909478 4021686 8113234 131927 2398048 1303926 740123 1129063 8163086 373627 9560476 5101913 7923503 8539677 2491612 2473137 9100369 5010628 8930326 1645133 5898108 7296945 5859080 2707904 2776890 3063810 1362087 3814785 9984322 2779891 2634791 893799 9317928 748025 3542077 1715975 4568302 4282199 5361389 2731387 4655826 4921864 7833299 5095680 5977892 2841262 85168 5078261 7851889 9015493 9239745 6266349 8828789 7615176 8974252 4122031 678985 336338 7936815 3179659 5632580 571605 6589809 4950507 3835981 131886 9182833 8404282 6930436 4544221 3652020 4102613 1982437 1485318 9198293 7960328 4326580 9283460 5554940 4694820 815305 4794685 961168 9644093 4926212 2451772 3766123 5605197 2788109 4219289 8784855 8420689 7307246 5374663 5887547 3659578 8022900 5070380 2063860 4953336 2130952 8232231 1572300 4113388 9717549 770592 4590068 6560480 2570404 145007 3771651 3385708 7456043 4732819 3029800 2382255 9700942 9312275 503803 2489050 3531563 1805009 3426090 3355160 9696023 9313637 7014738 235275 6900368 1594949 7704962 9031319 9827179 9277261 3144707 2061079 47853 7734774 8621558 2618256 396132 2393209 6003963 368527 9642379 1550114 5267133 9343320 3378740 8287287 4348721 9426655 92295 7774811 2781814 2304669 9604799 9796551 2539943 6505166 3907851 2761256 8052836 3735030 2038517 3713894 8312460 2086369 1448667 6934018 7220976 4361151 1843578 5741290 4729677 4002308 9807755 9996809 5861979 3186495 8284095 2727051 2613149 892741 3018213 5394962 5713761 2623011 7707865 770056 1644528 4132067 3531311 9697364 383448 5569827 3411257 8695908 172547 7376276 8146277 7393522 4253778 2506206 5651163 1499806 9024865 5458918 1496614 7403195 1161764 2297060 130245 6291264 5706152 3148458 4202577 3936264 8287820 1910441 4706319 2448700 8558860 8237630 4662415 8942307 6323808 590023 154566 6496355 7966298 8300842 6406228 4736427 807047 4573743 6236232 2348263 2549012 249197 9751457 3710775 5062608 9881702 2038 768759 5546511 4204614 7221375 6350682 8631407 1927693 8799381 7190266 2681674 3461795 8648924 9005482 4051818 8803490 8018188 4534467 9620683 6940767 9270894 2944082 1514509 8023477 5292344 4063520 8272674 5043801 290646 3335281 7441854 292683 6620392 5504716 7013649 3841766 1855397 8161407 8285810 654778 7868024 967484 6632924 6516947 2489317 684741 7836788 507504 7735560 7457471 7448270 9522805 2917904 1479131 7546281 8210247 5542650 5818954 5770399 5833296 1670587 5728604 8642330 8290978 3749671 8172330 4649095 5605068 6333736 2934904 8776197 4201759 3902387 5409120 3235058 6391703 8610213 1071845 9415558 6345772 1045667 9380180 5868576 3963570 859310 3414856 4690169 8918311 1750162 2976919 7267958 3420748 1221875 5910288 4228077 4971545 4082617 8877171 576612 2932705 1812074 1869160 7134463 8230813 7278280 369520 7138867 8404844 1441365 6554425 7266967 5003383 8450956 5651894 1483305 1826617 1583101 6173473 744927 3333262 1666743 8012885 9270361 2888617 6439524 3498437 7860162 3038492 2375607 953125 5971196 6704033 2822285 3105659 4934845 2616916 5991530 2073711 1021759 9949246 1144487 8288725 4952629 9595442 6456970 6435933 1422058 8040070 5125757 4683337 1373332 6792499 2696221 643692 2197468 1652096 4142129 57629 4690587 9034087 1010753 661783 5738119 6349389 6283793 672963 8966304 2275322 5263026 2504414 4740920 6407512 3309490 9693548 8519306 9766459 8645832 2457715 7806529 6287940 7141051 1696212 5596790 2353623 2339903 7794257 4005718 8998383 7851885 1212657 548822 1378990 4390791 6286940 7728378 674583 9476255 9211034 5466256 7255632 1715447 207175 3663143 5024937 2417074 4698800 7307747 3579257 7156515 5114275 9867196 6813917 6810486 5463986 9167540 1666741 5774594 5689609 3181475 3626479 6902265 3730296 7521820 3809407 2533588 5250197 4483989 4526194 6977582 2466597 1781825 8693029 5190123 7961319 6234317 123549 2660119 3542063 6219157 2332985 1172690 6086353 9146901 7983175 4066690 830792 2166267 9841283 9036753 5347742 5984113 8455369 9078037 3505932 2264776 4127976 1272481 9265116 8654169 8250062 4248064 435993 9459442 9438187 8397312 8210110 2078087 3573782 1752173 8297243 5906766 2924862 6899947 7570018 3424388 966636 917162 5590655 3324271 9953914 938396 9308383 925634 2532784 5330667 3190409 6660760 9119499 4971877 5314928 9885912 9219940 8267273 9345354 1174478 6664584 7555463 3252564 238365 1823987 4066159 8661482 7265200 966105 6231499 689588 4449093 7148660 6280242 7773363 9618925 9734989 9598097 544559 2267772 7445115 6251319 1444883 6564613 1223195 9276163 6450525 2959487 7543435 8312230 4133964 6724370 5867692 9902880 9479086 208031 3969038 8140567 7473230 4935142 6888417 8162817 9384234 6553429 6959410 9673948 6172353 6694398 9272045 9233263 1478522 9233511 5484582 5439756 5798124 9224128 4715918 4765000 2183614 4775704 3077229 8833930 1500073 1461272 8736809 979158 1669302 5222198 1636076 9142532 157339 8524493 9821700 2057925 5077921 6781110 4248224 1250273 5991859 6036620 2999888 9986732 5270131 8484469 5426488 1068254 224948 2658757 5833253 4924914 7434461 1426833 3758843 1450885 2888104 5012003 2430043 7073758 234200 4066118 8732641 2907890 2590610 8554340 7482166 184882 7851801 1730390 3951507 6360012 7767009 6951394
20
6346743
93037139
47952214
4289582
56621744
98177161
19464691
72454996
23102074
26899151
16398180
29377268
78350035
19286284
44389270
33296429
46360041
47139821
89878899
65092681
样例输出
1
2
5
1
:(
3
3
3
3
2