409604: GYM103643 G Shokugeki no Waifu

You've just challenged Soma to a shokugeki (food war)! The winner gets to hold hands with their favorite waifu!

In order to win, you need to craft the tastiest meal using $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ ingredients. The umami of the $$$i$$$th ingredient is $$$U_i$$$ and the sweetness of the $$$i$$$th ingredient is $$$S_i$$$ $$$(1 \leq U_i,\, S_i \leq 10^9)$$$.

To make the tastiest meal, the ratio of umami and sweetness is important. More specifically, for each ingredient, you need to make $$$U_i = K \cdot S_i$$$ $$$(1 \leq K \leq 10^4)$$$. In one second, you can choose either the umami or sweetness of a single ingredient and either increase or decrease it by $$$1$$$.

Find the minimum amount of time you need to make the tastiest meal.

The first line contains $$$2$$$ integers, $$$N,\, K$$$.

The next $$$N$$$ lines describe the ingredients. The $$$i$$$th of which contains $$$2$$$ integers, $$$U_i,\, S_i$$$.

Print the minimum amount of time you need to make the tastiest meal.

2 5
5 1
9 3

2

For the $$$1$$$st ingredient of the example, you don't change the umami or sweetness. Now, $$$U_1 = 5$$$ and $$$K \cdot S_1 = 5 \cdot 1 = 5$$$, so $$$U_1 = K \cdot S_1$$$. You spent $$$0$$$ seconds changing the umami and sweetness of the $$$1$$$st ingredient.

For the $$$2$$$nd ingredient of the example, you can spend a second increasing $$$U_2$$$ from $$$9$$$ to $$$10$$$. Then, you can spend another second decreasing $$$S_2$$$ from $$$3$$$ to $$$2$$$. Now, $$$U_2 = 10$$$ and $$$K \cdot S_2 = 5 \cdot 2 = 10$$$, so $$$U_2 = K \cdot S_2$$$. You spent $$$2$$$ seconds changing the umami and sweetness of the $$$2$$$nd ingredient.

In total, you spent $$$0 + 2 = 2$$$ seconds making the tastiest meal, which is the minimum.

$$$---------------------------------------------$$$

Problem Idea: codicon

Problem Preparation: codicon

Occurrences: Novice 6, Intermediate 3, Advanced 2