Vivek is bored with his plain walls in his room and decided to design one of the walls with laminates. He ordered some wall laminates for the wall that he wants to decorate.

He ordered N different sized (not necessarily unique) laminates to do the work.

The height of the wall as well as all the laminates is fixed and is the same.

There is a beauty factor assigned to each laminate which represents the beauty of the laminate. (Higher the beauty factor, more beautiful the laminate is)

Width of the wall is fixed and represented by the variable W.

Width of each laminate is represented by w₁, w₂, ... , w_N.

Beauty of each laminate is represented by b₁, b₂, ... , b_N.

Beauty of the wall is defined as the total of beauty of laminates pasted.

Also, there is a limit to the number of laminates to be pasted as pasting more and more laminates may degrade the overall beauty. This limit is represented by the variable L.

You need to maximise the beauty of the wall by pasting the laminates to the wall so that Vivek’s boring days are over in the best possible way.

NOTES

1. You must stay within the width of the wall.
2. Total width of laminates used may be less than the width of the wall.
3. Laminates cannot be pasted over each other and cannot be cut in pieces.

Input

• First line contains an integer W, the width of the wall.
• Second line contains two integers N and L, representing the number of laminates and maximum number of laminates that can be put on the wall respectively.
• Next N lines contain two integers w_i and b_i separated by space, representing width and beauty of each laminate respectively.

Output

• Single integer representing the maximum beauty that can be achieved.

Constraints

• $1 ≤ W ≤ 5000$
• $1 ≤ L ≤ N ≤ 50$
• $1 ≤ w_{i} ≤ 1000$
• $1 ≤ b_{i} ≤ 100$