D. Password

Codeforces

IDCF79D

Time1000ms

Memory256MB

Difficulty—

bitmasksdpshortest paths

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 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. She 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). Unfortunately she forgets how to type the password with only above operations. Determine the minimal number of operations required to enter her castle. ## Input The first line contains three integers _n_, _k_ and _l_ (1 ≤ _n_ ≤ 10000, 1 ≤ _k_ ≤ 10, 1 ≤ _l_ ≤ 100), separated by single spaces. The second line contains _k_ integers _x_1, ..., _x__k_ (1 ≤ _x_1 < _x_2 < ... < _x__k_ ≤ _n_), separated by single spaces. The 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. ## Output Print the minimal number of moves required to type the password. If it's impossible, print _\-1_. [samples] ## Note One 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.

Samples

Input #1

10 8 2
1 2 3 5 6 7 8 9
3 5

Output #1

Input #2

3 2 1
1 2
3

Output #2

\-1

API Response (JSON)

{
  "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 div...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments