GlobeX Cup '18 S2 - Test Scores

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

At the start of the semester, your teacher hands you a course outline. The outline states that there will be N tests, each of which will be out of M marks.

Your school has a weird scoring system. Instead of using percentages or letter grades, your school simply provides the average of your test scores on your report card.

You would like your parents to see a mark that is higher than or equal to K on your report card.

As of right now, you have predicted that for each test i (1 \leq i \leq N) that will happen, you will score x_i if you do not study at all. From there, you can increase your mark by 1 point for every y_i hours you study.

Find out the minimum total number of hours you need to study for all tests. Note that each test is weighted the same.

Input Specification

Line 1 contains integers N, M, and K, separated by a space. N is the number of tests throughout the semester. M is the number of marks that each test is scored out of. K is the minimum mark that you will accept on your report card.

Lines 2 to N + 1: The (i + 1)^{th} line contains the integers x_i and y_i, separated by a space, where 1 \leq i \leq N. x_i is the predicted score on test i if you do not study at all. y_i is the number of hours you need to study to increase your score by 1 on that test.

Output Specification

Output the minimum number of hours you need to study to get a mark of at least K on your report card.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^6
  • 0 \leq K,x_i \leq M
  • 0 \leq y_i \leq 10^6

Subtasks

Subtask 1 [10%]
  • 1 \leq N,M \leq 100
  • 0 \leq y_i \leq 100
Subtask 2 [30%]
  • 1 \leq N \leq 5000
  • 1 \leq M \leq 500
Subtask 3 [60%]

No additional constraints.

Sample Input

5 7 6
5 3
6 4
7 1
1 5
3 3

Sample Output

27

Sample Explanation

You can increase your score on the first test up to 7 by studying for 6 hours. You can then increase your score on the second test by 1 point with 4 hours of studying. You can increase your score on the fourth test by 1 point with 5 hours of studying. Finally, increase your score on the last test up to 7 by studying for studying for 12 hours.

Note that you cannot increase your score on any test to have a value of greater than 7 as the tests are out of 7 marks.


Comments


  • 0
    pblpbl  commented on Nov. 26, 2019, 10:51 p.m.

    Anyone know what's wrong with my code?