Brap Lesh Mafia

View as PDF

Submit solution

All submissions

Best submissions

Points: 5

Time limit: 1.0s

Memory limit: 16M

Author:

frenzybenzy

Problem types

PEG Test - Halloween 2014

The Brap Lesh Mafia is an organization that collects candy from unsuspecting neighborhoods during Halloween.

There are $N$ $N$ houses that the Brap Lesh Mafia will target on Halloween. The $i$ $i$ -th house will give out $a_i$ $a_{i}$ units of candy each time it receives a visitor, and will be visited $b_i$ $b_{i}$ times by members of the Brap Lesh Mafia.

There are $K$ $K$ members in the Brap Lesh Mafia. At the end of the day, the total amount of candy is divided evenly amongst its members such that each member receives the same amount of candy as any other member, and each member receives as much candy as possible. The leftover candy is fed to their pet dog, Rex.

Determine the amount of candy Rex will receive.

Input Specification

The first line of input will contain the integers: $N$ $N$ , $K$ $K$ $(1 \le N \le 10\,000; 1 \le K \le 1\,000\,000\,009)$ $(1 \leq N \leq 10 000; 1 \leq K \leq 1 000 000 009)$ .
$N$ $N$ lines of input will follow. The $i$ $i$ -th of these lines will contain values $a_i$ $a_{i}$ and $b_i$ $b_{i}$ $(0 \le a_i, b_i \le 10^9)$ $(0 \leq a_{i}, b_{i} \leq 10^{9})$ of house $i$ $i$ (for $1 \le i \le N$ $1 \leq i \leq N$ ).

Output Specification

Output a single integer, the number of units of candy that Rex will receive.

Sample Input 1

Copy

Sample Output 1

Copy

Explanation 1

Brap Lesh Mafia collects $71$ $71$ candies total. Split amongst $12$ $12$ , there are $11$ $11$ candies left over for Rex.

Sample Input 2

Copy

1 1000000007
1000000000 1000000000

Sample Output 2

Copy

Comments

6

Fattigger commented on Jan. 9, 2022, 8:17 p.m. ← edited →

I love Rex