DMOPC '17 Contest 2 P1 - 0-1 Knapsack - Olympiads Online Judge

DMOPC '17 Contest 2 P1 - 0-1 Knapsack

Points: 3

Time limit: 4.0s

Memory limit: 64M

Author:

Problem type

A classical problem in Computer Science is the 0-1 Knapsack problem. In this problem, you are given $N$ $N$ items with the $i$ $i$ th item takes up a capacity of $c_i$ $c_{i}$ and has a value of $v_i$ $v_{i}$ , and a knapsack with capacity $C$ $C$ , and try to maximize the sum of the value of the items in the knapsack while not exceeding the capacity of the knapsack.

Unfortunately, your knapsack has just broke (again). Since you can't fix it, you decide to get a new knapsack. Upon doing so, you shall attempt to solve the knapsack problem with this new knapsack. What size of knapsack will maximize the value of the items you can get?

Constraints

$1 \le N \le 10^5$ $1 \leq N \leq 10^{5}$
$-10^9 \le v_i \le 10^9$ $- 10^{9} \leq v_{i} \leq 10^{9}$
$0 \le c_i \le 10^5$ $0 \leq c_{i} \leq 10^{5}$

Input Specification

The first line will have a single integer $N$ $N$ , the number of items.
The next $N$ $N$ lines will each have two integers, $c_i$ $c_{i}$ and $v_i$ $v_{i}$ .