B. Significant Cups

Codeforces

IDCF774B

Time3000ms

Memory256MB

Difficulty—

binary searchdata structurestwo pointers

Stepan is a very experienced olympiad participant. He has _n_ cups for Physics olympiads and _m_ cups for Informatics olympiads. Each cup is characterized by two parameters — its significance _c__i_ and width _w__i_. Stepan decided to expose some of his cups on a shelf with width _d_ in such a way, that: * there is at least one Physics cup and at least one Informatics cup on the shelf, * the total width of the exposed cups does not exceed _d_, * from each subjects (Physics and Informatics) some of the most significant cups are exposed (i. e. if a cup for some subject with significance _x_ is exposed, then all the cups for this subject with significance greater than _x_ must be exposed too). Your task is to determine the maximum possible total significance, which Stepan can get when he exposes cups on the shelf with width _d_, considering all the rules described above. The total significance is the sum of significances of all the exposed cups. ## Input The first line contains three integers _n_, _m_ and _d_ (1 ≤ _n_, _m_ ≤ 100 000, 1 ≤ _d_ ≤ 109) — the number of cups for Physics olympiads, the number of cups for Informatics olympiads and the width of the shelf. Each of the following _n_ lines contains two integers _c__i_ and _w__i_ (1 ≤ _c__i_, _w__i_ ≤ 109) — significance and width of the _i_\-th cup for Physics olympiads. Each of the following _m_ lines contains two integers _c__j_ and _w__j_ (1 ≤ _c__j_, _w__j_ ≤ 109) — significance and width of the _j_\-th cup for Informatics olympiads. ## Output Print the maximum possible total significance, which Stepan can get exposing cups on the shelf with width _d_, considering all the rules described in the statement. If there is no way to expose cups on the shelf, then print 0. [samples] ## Note In the first example Stepan has only one Informatics cup which must be exposed on the shelf. Its significance equals 3 and width equals 2, so after Stepan exposes it, the width of free space on the shelf becomes equal to 6. Also, Stepan must expose the second Physics cup (which has width 5), because it is the most significant cup for Physics (its significance equals 5). After that Stepan can not expose more cups on the shelf, because there is no enough free space. Thus, the maximum total significance of exposed cups equals to 8.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Significant Cups",
    "description": {
      "content": "Stepan is a very experienced olympiad participant. He has _n_ cups for Physics olympiads and _m_ cups for Informatics olympiads. Each cup is characterized by two parameters — its significance _c__i_ a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF774B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Stepan is a very experienced olympiad participant. He has _n_ cups for Physics olympiads and _m_ cups for Informatics olympiads. Each cup is characterized by two parameters — its significance _c__i_ a...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments