PEG Test - Halloween 2014

Problem B: Brap Lesh Mafia

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

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

There are 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 Format

The first line of input will contain the integers: N, K (1 ≤ N ≤ 10000; 1 ≤ K ≤ 1000000009).
N lines of input will follow. The i-th of these lines will contain values a_i and b_i (0 ≤ a_i ≤ 10⁹; 0 ≤ b_i ≤ 10⁹) of house i (for 1 ≤ i ≤ N).

Output Format

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

Sample Input 1

4 12
1 4
2 9
3 8
5 5

Sample Output 1

11

Explanation 1

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

Sample Input 2

1 1000000007
1000000000 1000000000

Sample Output 2

49

All Submissions
Best Solutions

Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 07, 2014
Author: frenzybenzy

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

there are a couple of problems, first, you are using long to scan integers, which basically means you can't scan anything bigger than a integer, secondly, each value can be as big as 10^9, which a integer should hold, but since there can be up to 10000 numbers as big as 10^9, that means you need something that can hold up to 10^13, which is already bigger than the integer data type , and since you are dealing with multiplication, you might go overflow even with long so to solve this, first use long and sc.nextlong, and use the mod to your advantage, good luck

Still, I changed everything to long and sc.nextLong, and its the same.

Since this program seems to use very large numbers, is there any algorithm commonly used with very large numbers greater than (2^64)-1 ? Kind of like the bubble sorting, except for large numbers. 
I'm planning to 'make' an algorithm which multiplies large numbers in the way that people do it by hand, then storing it in a string or array of integers. Before I start however, I want to know if there is any standard algorithm designed for this.
Also, unsigned long long int is the largest integer value datatype, right?

Numbers larger than unsigned long long int are not required for this problem.