By Elder Sobrinho, UFTM Brazil
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).
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.
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:
We can observe that when k is an integer value, the quantile will be Xk, that is, Qj = Xk, where:
In addition, the lower and upper limit of the boxplot is calculated as: Q1 – 1.5(Q3 – Q1) and Q3 – 1.5(Q3 – Q1).
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).
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|