Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

MonoMono

By ishtupeed · Limits 500ms, 128 MB

You have probably heard of the famous board game, Monopoly. According to Wikipedia, in this game, players roll two six-sided dice to move around the game board, buying and trading properties, and developing them with houses and hotels. Players collect rent from their opponents, with the goal being to drive them into bankruptcy.

Today you will be playing a single-player version of the game: MonoMono. In MonoMono, there are n properties denoted by P0, P1, ..., Pn-1 arranged in a directed cycle. You will start at P0 with t kata (unit of currency in MonoMono), and then repeatedly roll two 6-sided dice (each numbered from 1 to 6). After each roll, you will move from one property to another. The move is determined by the sum of the outcome of the roll. So after each roll, you can move between 2 to 12 spaces forward along the directed cycle based on the outcome. For example, if n = 10 and the first roll has an outcome 6, you will move to P6. If the second roll has an outcome 8, you will move to P4 (shown in the picture below).

You own m properties. Each property Pi has a transit cost Ci: when you move to Pi, you gain Ci kata if you own the property, and loss Ci kata otherwise. You don't lose or gain any money for P0 at the very beginning of the game.

Since you are busy participating in this programming contest and have to solve as many problems as possible quickly, you want to find the minimum number of turns required to at least double your starting money, without ever going bankrupt (having a negative balance).

Input

The first line of input contains three integers, n, t, and m, denoting the number of properties, starting amount, and number of properties owned by you, respectively.
The next line contains n space-separated integers. Each integer Ci denotes the transit cost of the Pith property.
The following line contains m distinct space-separated integers. Each integer i denotes that you own property Pi.

Constraints

  • n, t > 0
  • n × t ≤ 105
  • 0 ≤ m ≤ n
  • 0 ≤ Ci ≤105
  • 0 ≤ i < n

Output

If it is not possible to achieve the goal stated, print "-1" (without the quotes). Otherwise, print a single integer denoting the answer.

Sample

InputOutput
3 10 3
10 10 10
0 1 2
1

Discussion

Statistics


75% Solution Ratio

ishtupeedEarliest, Apr '20

Exo_TicFastest, 0.0s

ishtupeedLightest, 1.7 MB

ishtupeedShortest, 1368B

Submit

Login to submit