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
  • C++ Reference
  • About
    • Help
    • Terms of Use
    • Technical Specifications
    • Credits

lunchcombo 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

A restaurant is offering a special lunch combo, consisting of a single main course and a side dish. There are a total of M main courses and S sides, with the ith main course costing Ai dollars and the ith side dish costing Bi dollars. The cost of a particular lunch combo is simply the sum of the cost of the main course and side dish.

Peanut wants to treat a total of K of his friends to a lunch combo each, but he wishes that no two friends receive the same combo. Two combos are considered to be different if either the main course or side dish (or both) differs. Help Peanut figure out the minimum cost, in dollars, he would have to spend on this treat.

Input

The first line of input will contain three integers, M, S and K.

The second line of input will contain M integers, representing the array A.

The third line of input will contain S integers, representing the array B.

Output

The output should contain a single integer, the minimum cost, in dollars, Peanut would have to spend on his treat.

Limits

For all subtasks: 1 ≤ M, S ≤ 300 000, 1 ≤ K ≤ MS, 1 ≤ Ai, Bi ≤ 106.

Subtask 1 (35%): 1 ≤ M, S ≤ 1000.

Subtask 2 (24%): 1 ≤ K ≤ 300 000.

Subtask 3 (41%): No additional constraints.

Sample Input

3 3 3
3 2 5
3 2 1

Sample Output

11

Explanation

The first friend would receive main 2 and side 3 ($2+$1 = $3). The second friend would receive main 2 and side 2 ($2+$2 = $4). The third friend would receive main 1 and side 3 ($3+$1=$4). The total cost would therefore be $3+$4+$4=$11.

Tags

Binary Search

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
135111s256MBMinimum
224211s256MBMinimum
341311s256MBMinimum
4011s256MBMinimum

Judge Compile Command

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

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 28.10.19A
Copyright © 2019 mrJudge. All rights reserved.

Under Construction

Stats Tab Content

Under Construction too