Alice enjoys playing a card game called Steadily Growing Steam (as known as SGS).

In this game, each player will play different roles and have different skills. Players get cards from the deck and use them to play the game. Each card has a numeric label , the point number. In addition, each card has a value .

Now Alice is playing this game with Bob. According to the skill of Alice's role, she can have Bob display cards from the top of the deck. After that, Bob must choose some cards from the cards and split the chosen cards into two sets that the sum of the cards' point numbers in the two sets are equal. In other words, if one of the sets is and another is , and (Note that is not necessary). Then, Alice gets all of the cards in set and Bob gets the cards in set .

However, according to the skill of Bob's role, before choosing the two sets, he can choose at most different cards and double their point numbers. In other words, he can choose a sequence and for each , change into . After that he can continue choosing the two sets.

Alice and Bob are partners in this game. Now given the cards from the deck, they want to know the maximum possible sum of the values of the cards they finally get. In other words, determine the maximum among all valid schemes(choose cards to double their point numbers, then choose cards and split them into two sets of the same point number sum) and output it.

The first line contains two integers  and , denoting the number of the displayed cards and the maximum number of cards that Bob can choose to double their point numbers, respectively.

The  line contains two integers  and , denoting the value and the point number of the -th card, respectively.

Output one line containing one integer, denoting the maximum sum of the value of the cards that Alice or Bob can get.

4 1
10 1
-5 3
5 1
6 1

21

One possible scheme:

Double  and choose that , where the point number sum are both 2, and the sum of the card values is .