oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

nutritionist Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

statement.html

Problem Description

Guan is a nutritionist looking for clients. He has a total of N potential clients, each with a calorie count Ci and a price Pi that the client would pay Guan if Guan chose to take this client up.

However, Guan faces a very big problem. His company insists that he "specialises" in a field, so the difference between the maximum calorie intake of all his clients and the minimum calorie intake of all his clients must not exceed L. Also, Guan can only take up a maximum of K clients. Help Guan earn the maximum amount of money possible.

Subtasks

Subtask 1 (9%): 1 ≤ K ≤ N ≤ 100. 1 ≤ L ≤ 100. Pi = Ci = 1.
Subtask 2 (17%): 1 ≤ K ≤ N ≤ 100. 1 ≤ L, Pi, Ci ≤ 100.
Subtask 3 (25%): 1 ≤ K ≤ N ≤ 500. 1 ≤ L, Pi, Ci ≤ 500.
Subtask 4 (49%): 1 ≤ K ≤ N ≤ 200 000. No integer in the input will be more than 32-bit.

Input

The first line of input will contain three integers, N, K and L.
The next N lines will contain two integers each, referring to the calorie count and the price of the client respectively.

Output

The output should contain one integer, the maximum amount of money Guan can get.

Sample Input 1

7 3 6
3 7
5 9
7 3
11 2
13 6
14 8
15 3

Sample Output 1

19

Tags

Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
19201s64MBMinimum
217401s64MBMinimum
325601s64MBMinimum
449801s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o nutritionist -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.