Jesse is going on a shopping spree in HackerLand. He wants to buy items. In HackerLand, all shops are specialized in selling only one type of item. Therefore, Jesse can purchase only one item for every distinct shop that he visits.
HackerLand shops are located on a number line with buildings, , where each building is located at coordinate . The value at each index indicates whether the shop at sells an item or not. means building sells the item that Jesse needs, and means it does not.
The distance between two buildings, and , is .
Jesse always starts from his house at building . As he buys more items, he has to carry heavy bags so his speed reduces by a travel constant, . The travel time between and , is calculated as follows:
- If he has not purchased any items, his travel time is minutes.
- If he has already purchased items, his travel time is minutes.
Given , , , and a map of HackerLand, find and print the minimum time (in minutes) needed to purchase items from distinct shops. If he cannot buy all items, print -1 instead.
Note: Building will not sell the items that Jesse needs. There are not always exactly shops and Jesse cannot travel backwards.
Input Format
The first line contains three space-separated integers describing the respective values of (the number of shops), (the number of items to purchase), and (the travel constant).
The second line contains space-separated binary integers describing whether the respective building sells the items or not.
Constraints
Output Format
Print the minimum number of minutes taken by Jesse to purchase items from distinct shops. If it's not possible, print -1 instead.
Sample Input 0
7 1 3
0 0 0 1 0 0 0
Sample Output 0
3
Explanation 0
The city has buildings, Jesse wants to buy item, and the travel constant is . The only building that sells the needed items is , so Jesse must travel to that building to buy his first (and only) item. Because he always starts out with items, it only takes him one minute to travel from building to building; this means that it takes him a total of minutes to travel from to and purchase the item. Thus, we print as our answer.
Sample Input 1
11 4 3
0 0 0 1 0 1 0 1 1 1 0
Sample Output 1
26
Explanation 1
The city has buildings, Jesse wants to buy items, and the travel constant is . There are shops, and they're located in buildings , , , , and . Jesse minimizes the amount of time it takes to purchase all items by buying them from , , , and in the following way:
- Start at and travels to in minutes and purchases item, so he now has total items.
- Travel from to in minutes and purchases items, so he now has total items.
- Travel from to in minutes, so he now has total items.
- Travel from to in minutes, so he now has total items.
Now that is equal to , his journey is complete. We then print his total travel time, which is .