Suppose we are to play a game in which we have a group of cards with 2 numbers on them. One number is how many points the card is worth, and the other number is how much the card costs. You are given a set allowance you can spend on buying cards. Once you buy a card, you are not allowed to purchase the card again. Your goal is write a program in Java called Game01 that will find the maximum score you can make with the set allowance given. You do not need to necessarily spend all the allowance, but you cannot spend more than the allowance. The program should simply print the maximum score.

Input

The input to your program is a file called in.txt. You can safely assume this file will be in the same location as your program. The format of this file is as follows.

1. The first line contains your given allowance. It is a single integer greater than or equal to 0.

2. The next N lines each contain two numbers representing the points and cost respectively.

a. The points will be random nonzero positive integer values.

b. The costs will be random nonzero positive integer values.

c. The number of cards, N, is random but there will at least be 1 card.

3. There may be duplicate cards with either the same point value and same cost or same point value and different costs.

Output

The output of your program should be a single integer that is the maximum score that can be made by purchasing cards.

Examples

The following examples are not representative of the format in.txt will have. For the format, refer to the Input section.

Allowance 5

[6, 2], [8, 2], [4, 2], [7, 1], [7, 1], [3, 2] ? The maximum score is 22. The cards bought are [8, 2], [7, 1], [7, 1] where the final cost is 4.

Allowance 5

[10, 1], [8, 10], [10, 3], [7, 2], [3, 2] ? The maximum score is 20. The cards bought are [10, 1], [10, 3] where the final cost is 4.

Allowance 15

[5, 12], [10, 8], [4, 6], [5, 8] ? The maximum score is 14. The cards bought are [10, 8] and [4, 6] where the final cost is 14.

Allowance 15

[5, 4], [1, 4], [2, 4], [4, 2], [2, 5], [4, 1], [2, 2] ? The maximum score is 17. The cards chosen were [5, 4], [2, 4], [4, 2], [4, 1], [2, 2]. The final cost is 13.

In.txt File is

35

88 12 94 20 88 17 52 14 69 14 98 10 92 10 77 20 53 11 77 17

Criteria

To receive maximum points for this assignment you must follow the guidelines presented here.

1. You must implement and utilize a singly linked list. The linked list must be written from scratch by you. Only implement the necessary methods that will help you solve the problem. Try to keep your linked list implementation minimal.

a. You may not use the built-in list implementations in the Java library. This includes Linked List and Array List.

b. Each node of the linked list must include only three elements: two integer types and a reference to the next element of the list. The nodes represent the cards.

c. You may not have more than one instance of a linked list.

2. Read the cards data from a file called in.txt as specified in the input section of this document. You can assume this file is in the same location as your program.

a. No calculations are permitted while reading in the data from in.txt.

b. Once the data is read into your linked list, you may not manipulate the data or the list. For example, you may not sort, shuffle, remove, or add to the list. Once the cards have been read in, the list must remain the same throughout the life of the program.

c. Your program may not modify the file at all. It should perform read-only operations.

3. No additional data structures are allowed. This includes arrays, strings, trees, etc. All computations must be done in place in the original linked list (section 2b). Your program may use auxiliary scalar variables and reference variables (used to point to nodes of the list).

a. There is only one exception to the rule and that is when you are reading in the data you may use strings. This is also the only time you may use the standard library as well. For example, you can use StringTokenizer and/or the Scanner library.

4. Bit masking is not allowed and is not a solution. Use of an array of Booleans or integers is also disallowed according to guideline 3.

5. All code should be placed in one .java file and must be able to be compiled and ran from that .java file. Inner classes are allowed. Again, try to write short and simple programs. I/O, exception handling, and the linked list implementation should be kept to a minimum.