Idea: Find the truth assignment which satisfies as many of the given clauses as possible. Input Format: The input file will be called input3.txt and be in the same directory as the java and class files. The file will contain n lines and each line will consist of 2 non-zero integers. A positive value i will indicate the boolean variable r, and a negative value j will indicate the boolean variable rui- The two values on each line will represent the disjunction of those two variables. For example, if the file contained, -1 3 -2 3 would represent the set of clauses V2, You will be asked to determine either VV,Vz) 1. The true optimal solution (probably calculated by brute force) 2. A pretty good solution (using some reasonable idea you think up). Output: A number N which is the number of clauses satisfied and a truth assignment which achieves that number Examples: If the input was 1 2 2 3 2 3 -2-3 Your program should interact with the user as follows Would you like 1) True Optimal Solution (slou) 2) Pretty Good Solution (fast) TTF Your program should interact with the user as follows Hould you like 1) True Optimal Solution (slou) 2) Pretty Good Solution (fast) The exact results from the second trial need not be exactly 7, but it is acceptable to not find the true optimal solution. Details: The program must be written in Java. The program must compile with the command javac java and run with the command java Project3. One common problem students have with this is placing the classes into packages. Don't do this just use the default package). The program should be reasonably commented, indented