{"problem":{"name":"D. Password","description":{"content":"Finally Fox Ciel arrived in front of her castle! She have to type a password to enter her castle. An input device attached to her castle is a bit unusual. The input device is a 1 × _n_ rectangle div","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF79D"},"statements":[{"statement_type":"Markdown","content":"Finally Fox Ciel arrived in front of her castle!\n\nShe have to type a password to enter her castle. An input device attached to her castle is a bit unusual.\n\nThe input device is a 1 × _n_ rectangle divided into _n_ square panels. They are numbered 1 to _n_ from left to right. Each panel has a state either ON or OFF. Initially all panels are in the OFF state. She can enter her castle if and only if _x_1\\-th, _x_2\\-th, ..., _x__k_\\-th panels are in the ON state and other panels are in the OFF state.\n\nShe is given an array _a_1, ..., _a__l_. In each move, she can perform the following operation: choose an index _i_ (1 ≤ _i_ ≤ _l_), choose consecutive _a__i_ panels, and flip the states of those panels (i.e. ON → OFF, OFF → ON).\n\nUnfortunately she forgets how to type the password with only above operations. Determine the minimal number of operations required to enter her castle.\n\n## Input\n\nThe first line contains three integers _n_, _k_ and _l_ (1 ≤ _n_ ≤ 10000, 1 ≤ _k_ ≤ 10, 1 ≤ _l_ ≤ 100), separated by single spaces.\n\nThe second line contains _k_ integers _x_1, ..., _x__k_ (1 ≤ _x_1 < _x_2 < ... < _x__k_ ≤ _n_), separated by single spaces.\n\nThe third line contains _l_ integers _a_1, ..., _a__l_ (1 ≤ _a__i_ ≤ _n_), separated by single spaces. It is possible that some elements of the array _a__i_ are equal value.\n\n## Output\n\nPrint the minimal number of moves required to type the password. If it's impossible, print _\\-1_.\n\n[samples]\n\n## Note\n\nOne possible way to type the password in the first example is following: In the first move, choose 1st, 2nd, 3rd panels and flip those panels. In the second move, choose 5th, 6th, 7th, 8th, 9th panels and flip those panels.","is_translate":false,"language":"English"}],"meta":{"iden":"CF79D","tags":["bitmasks","dp","shortest paths"],"sample_group":[["10 8 2\n1 2 3 5 6 7 8 9\n3 5","2"],["3 2 1\n1 2\n3","\\-1"]],"created_at":"2026-03-03 11:00:39"}}