33661번 - Nearest Nice Numbers 스페셜 저지다국어

문제

While typical programming contests try to strike a balance between different types of problems (geometry, graphs, dynamic programming, number theory, strings, etc), at the User-Aligned Programming Competition (UAPC), the contestants decide in advance what types of problems they want to see by voting in a survey. The survey format is simple: each contestant picks their single favorite type of problem among $N$ options. Then, each problem type $i\in \{1,2,\dots ,N\}$ is assigned a number $x_i \in [0,1]$ based on what share of the votes it received. So, we must have $\sum_{i=1}^{N}{x_i=1}$.

Unfortunately, many of the $x_i$ values came back with an unsightly number of decimal places due to the extremely large number of survey responses, which is not suspicious at all. To fix this, your job is to replace each $x_i$ with an integer $f_i$ so that the fraction $\frac{f_i}{D}$ (for a given $D$) approximates $x_i$. You must pick the $f_i$ values in a way that minimizes $\sum_{i=1}^{N}{|D\cdot x_i - f_i|}$ and ensures that $\sum_{i=1}^{N}{f_i=D}$.

입력

The first line of input contains two integers $N$ (2ドル≤N≤10^5$) and $D$ (1ドル≤D≤10^9$) where $N$ is the number of problem types and $D$ is the denominator to use. Then $N$ lines follow, with line $i$ containing the single number $x_i$.

출력

Output the minimum possible value of $\sum_{i=1}^{N}{|D\cdot x_i- f_i|}$ over all choices of $f$. Answers with an absolute or relative error of at most 10ドル^{-6}$ will be accepted.

제한

힌트