URI Online Judge | 3164

Inspection on Company

By Elder Sobrinho, UFTM BR Brazil

Timelimit: 3

Mario is an inspector, every day he visits a company and asks them for a list containing the weight of the trees cut by the company in the last 30 days. Through empirical observation, it is known that the data always follow a normal distribution and the company will pay a penalty X when the data set presents extreme values according to the statistical rules of the boxplot chart. Since X is calculated as follows: X = PV, where P is the number of observations considered extreme by the boxplot and V is the unit value of the penalty established in the inspection rules. Your task is to calculate the value of the penalty according to a given data set and the unit value of the penalty.

Background p/ Boxplot:

The boxplot is a graph used to assess the empirical distribution of a data set. This is formed by the first and third quartiles, presenting the median (Q2) between these quartiles (see figure below). The lower and upper stems that extend from the lower quartile (Q1) and the upper quartile (Q3), denote the minimum and maximum limits. Therefore, values outside this range are considered extreme values (outliers).

3462_a.png

In summary, quartiles are values given from a set of observations ordered in ascending order, which divide the distribution into four equal parts. The first quartile, Q1, is the number that leaves 25% of the observations below and 75% above, while the third quartile, Q3, leaves 75% of the observations below and 25% above. Q2 is the median, leaving 50% of the observations below and 50% of the observations above. The figure below shows this relationship according to the data distribution, in this case, a normal distribution.

3462_b.png

Objectively, the calculation of the boxplot thresholds (Q1, Q2 and Q3) is given by: Let n be the total number of elements in the sample, calculate j(n+1)/4, for j=1, 2 and 3. Thus Qj will be an element between Xk and Xk+1, where k is the largest integer less than or equal to j(n+1)/4 and will calculated as:

3462_c.png

We can observe that when k is an integer value, the quantile will be Xk, that is, Qj = Xk, where:

3462_d.png

In addition, the lower and upper limit of the boxplot is calculated as: Q1 – 1.5(Q3 – Q1) and Q3 – 1.5(Q3 – Q1).

Input

The entry contains several test cases. The first line of each case contains two numbers N (1 ≤ N ≤ 106) and P (1 ≤ P ≤ 106), representing the number of elements on the list that contain the weights of the cut trees and the unit value of the penalty established in the regulations, respectively. The second line of each case contains the n-th weights of the trees cut by the company (0 ≤ ni ≤ 90000). The entry ends with end-of-file (EOF).

Output

For each test case, print the amount of the penalty (Xi) that the company will pay to the government (0 ≤ Xi ≤ 109).

Input Sample Output Sample

27 350
836962 670005 760702 418543 305993 586022 439392 806735 789441 805297 693606 641947 731631 762916 687297 577964 608574 338189 742702 740253 414602 422863 842306 796430 783221 410343 507054
125 1846
466565 533097 662830 747738 538861 785591 732920 516169 381282 332191 650453 511281 512419 407361 629718 496882 687915 466148 658433 330061 602968 695330 400290 877885 450114 803743 563465 545334 630502 740911 616578 536530 730177 647438 602675 488436 644958 743645 746834 606122 640365 431670 453651 581547 736512 588121 425169 484183 518946 326952 304295 507567 560948 413374 609377 318756 387983 669662 559285 713625 470320 486861 597232 587713 395933 797989 876572 575586 879872 694684 766020 692250 707191 873597 344292 564383 525518 806957 669805 829583 330544 670811 742504 591918 852958 788451 650196 435672 413123 585054 424806 691486 708922 592543 372976 692536 630824 569753 724519 718326 402952 794537 503779 675800 386097 809345 662112 468372 474019 671663 464763 814395 547938 890146 472567 557276 578567 790490 595460 330056 734208 480924 552863 821822 686318

0
27690