LearnToCP
Sign in
Navigation
HomeRoadmapProblemsAbout Us
Theory
Contest Knowledge
Selecting an IDEInteractive TasksOutput-Only Tasks
Basics
Your First ProgramData types and IOC++ syntaxModuloFunctionsVectorsMatricesTime Complexity
Sorting
SortingCounting sortRadix Sort
Optimization Techniques
Two PointersSum of numbers 1 to nPrefix sumBinary SearchGreedyBinary Search FunctionsBinary Search by AnswerDivide and Conquer
Binary Numbers
Binary NumbersNumbers in codeBitwise OperationsBitmasks
Math
Binary ExponentiationPrime NumbersPrime FactorizationGCD and LCMSieve of EratosthenesModified Sieve
Data Structures
StringsStackQueueMapsSetsPriority QueueCustom Criteria for FunctionsSegment TreesFenwick TreesSparse TablesUnion FindSqrt Decomposition
Combinatorics
Addition PrincipleMultiplication PrincipleCombinatoric ObjectsInclusion Exclusion Principle
Geometry
Geometry BasicsVectorsCross and Dot ProductLinesPolygonsAnglesPoint in PolygonDistances and Intersection PointsConvex HullCircles
Recursion
PointersRecursionGenerating Combinatoric Objects
Dynamic Programming
About DPDP problemsTree DPBitmask DP
Graph Theory
GraphsDFS and BFSShortest PathsTreesTopological SortingDijkstra's AlgorithmMinimum Spanning TreesShortest Path Algorithms
Advanced Graph Theory
BiconnectivityStrongly Connected ComponentsBipartite GraphGraph FlowAugmenting PathsFlow - Minimum Cut DualityHeavy-Light DecompositionCentroid Decomposition
Advanced Data Structures
2D and 3D Segment TreesLazy PropagationImplicit Segment TreesPersistent Segment TreesLowest Common AncestorTrieBalanced Binary Search TreesMo's Algorithm

Knapsack Problem

EasyProblem #8
Time LimitMemoryInputOutput
1 s64 MBstdinstdout

One of the most famous DP problems. The state depends on two things: which items we considered, and how much capacity is left.

A thief broke into a warehouse carrying a knapsack that can hold at most W kilograms. In the warehouse there are n items, each with a weight and a value. Every item can be taken at most once, and items cannot be split.

Determine the largest total value of items the thief can carry out, such that their total weight does not exceed W.

Input

First line of input will be two numbers: n and W, the number of items and the capacity of the knapsack.
In the next n lines will be two numbers each: wi​ and vi​, the weight and the value of the i-th item.

Output

A single number - the largest total value that fits in the knapsack.

Example

Input
4 5
4 1
5 2
1 3
3 4
Output
7

The thief takes the third and the fourth item: total weight 1+3=4≤5, total value 3+4=7.

Constraints

1≤n≤100
1≤W≤104
1≤wi​≤W
1≤vi​≤106

Submit your solution

Sign in to submit your solution and track your progress.

Sign in to submit