We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Turn Off the Lights

Turn Off the Lights

Problem
Submissions
Leaderboard
Discussions
Editorial

There are bulbs in a straight line, numbered from to . Each bulb has a button associated with it, and there is a cost, , for pressing this button. When some button is pressed, all the bulbs at a distance from bulb will be toggled(off->on, on->off).

Given , , and the costs for each button, find and print the minimum cost of turning off all bulbs if they're all on initially.

Input Format

The first line contains two space-separated integers describing the respective values of and .
The second line contains space-separated integers describing the respective costs of each bulb (i.e., ).

Constraints

Output Format

Print a long integer denoting the minimum cost of turning off all bulbs.

Sample Input

3 1
1 1 1

Sample Output

1

Explanation

If we press the middle switch, the middle bulb and the closest adjacent bulbs (i.e., the first and third) will turn off. Because all bulbs will be off in one button press, this cost is minimal. Thus, we print as our answer.

Author

coolbun

Difficulty

Hard

Max Score

70

Submitted By

1095

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature