Reducing 3SAT to MAX-3SAT I have the following problem:


  Consider the MAX-3-SAT problem: given a Boolean function in
  Conjunctive Normal Form (CNF) determine the maximum number of clauses
  that can be satisfied. Prove that this problem is NP-hard.


I know that I'd have to reduce 3-SAT to MAX-3SAT, but I'm pretty lost on how that would work. The related decision problem I figured would be, given clauses and a number k, is there an assignment satisfying at least k of the clauses?
Hint: You have a 3SAT formula $\varphi$ in CNF with $n$ clauses and a maximal $m \le n$ number of clauses can be satisfied. What happens if $m &lt; n$? And what about $m = n$?