Maximize the Earning

Napoleon choosed a city for Advertising his company’s product. There are 

$S$

 streets in that city. Each day he travels one street. There are 

$N$

 buildings in a street which are located at points 

$1,2,\mathrm{3\dots .}N($

$respectively)$

. Each building has some height(Say 

$h$

 meters). Napoleon stands at point 

$0$

. His height is 

$0.5m$

. Now Napoleon starts communicating with the people of each building. He can communicate with people of a particular building only if he can see that building. If he succeed to communicate with any particular building then his boss gives him 

$Rrupees$

. i.e. if he communicates with 

$K$

 buildings in a day, then he will earn 

$K\ast Rrupees$

. Now Napoleon wants to know his maximum Earning for each day.

Note: All the points are on Strainght Line and Napoleon is always standing at point 0.

Input:
First line of input contains an integer 

$S$

, denoting no of streets in the city.
Details for each street is described in next two lines.
First line contains two integers 

$N$

 and 

$R$

$,$

 denoting no of buildings in the Street and earning on communicating with a building.
Second line contains 

$N$

 integers, denoting height of  building.

Output:
Print 

$S$

 Lines, each containing maximum earning in 

$i^{th}$

 street.
    
Constraints:
    

$1\le N\le {10}^4$

    

$1\le h\le {10}^9$

    

$1\le S\le 100$

    

$1\le R\le {10}^4$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

There are two streets in the city.

The first street has 

$6$

 buildings and the earning of Napoleon for communicating with each building is 

$3rupees$

.

Height of buildings are 

$8,2,3,11,11,10$

 respectively.

As Chef is standing at point 

$0$

, he will be able to see only 1st and 4th building.

So his total earning will be 

$3\ast 2=6rupees$

 in that street

Similarly for 2nd street his earning will be 

$60rupees$

int main()

    long int n,s,r,i;

    long long int max,h,building;

    scanf(“%ld”,&s);

    

    while(s–)

    {

        scanf(“%ld%ld”,&n,&r);

         max=0;

        building=0;

    for(i=0;i<n;i++)

        {

      scanf(“%lld”,&h);

      if(h>max)

           {

               max=h;

               building++;

           }

        }

        printf(“%lldn”,r*building);

    }

    return 0;