409896: GYM103828 I Bombing buildings

COVID-22 has spread in Aws's City. since humanity had suffered a lot from COVID-19, the army made a decision to destroy Aws's city.

Aws's City consists of $$$n$$$ buildings lined up in a row from left to right, the height of the $$$i$$$-th building is $$$h_i$$$.

The army has two types of bombs.

• The first type of bombs can be used to destroy exactly one building with a cost of $$$x$$$
• The second type of bombs can be used to destroy a whole neighborhood with a cost of y.

A neighborhood is a segment (consecutive sequence) of buildings $$$[l,r]$$$ $$$(l < r)$$$ where $$$(h_l, h_r > 0)$$$ and $$$h_r$$$ is the first building to the right of $$$h_l$$$ greater than or equal to $$$h_l$$$ (in other words, all buildings in the segment $$$[l+1,r-1]$$$ have heights less than $$$h_l$$$.

The army wants you to find the minimum cost to destroy all city buildings.

The first line of the input contains a single integer $$$T$$$, the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$x$$$, and $$$y$$$ $$$(1 \le n \le 500)$$$ $$$(1 \le x,y \le 10^9)$$$ the number of buildings in the city, the cost of destroying one building, and the cost of destroying a neighborhood respectively.

The second line of each test case contains $$$n$$$ integers describing the height of each building in Aws's city from left to right where $$$h_i$$$ $$$(1 \le h_i \le 10^9)$$$ is the height of building number $$$i$$$.

The sum of $$$n$$$ over all test cases doesn't exceed $$$500$$$.

For each test case, print a single integer representing the minimum possible cost to destroy all buildings in the Aws's city.

3
5 5 7
2 1 3 1 5
5 10 10
10 8 5 10 1
1 1 5
10

12
20
1

For the 1-st test case: First, destroy the building with index 3 using the first bomb with cost $$$x$$$. The city will become like this [2 1 0 1 5]. Then, destroy a neighborhood from index 1 to index 5 with a cost of $$$y$$$. The total cost to destroy all the buildings = 1*$$$x$$$ + 1*$$$y$$$.

For the 2-nd test case: First, destroy a neighborhood from index 1 to index 4 with cost y. The city will become like this [0 0 0 0 1] Then, destroy the last building using the first bomb with cost x. The total cost to destroy all the buildings = 1*$$$x$$$ + 1*$$$y$$$.

For the 3-rd test case: The only way to destroy the only building in the city is by using the first bomb with cost $$$x$$$.