Fat Brother and Maze are fans of amusement parks. They always go there on the weekend and play different kind of games. This weekend they found a challenging one, a target shooting game. There are N targets place along a straight line from left to right with number from 1 to n. For the ith target, Fat Brother can get three possible points when he shoots this target: ai, if there are no neighbor targets chosen; bi, if one neighbor targets chosen; ci, if both neighbor targets chosen.
Now Fat Brother wants to know how to choose the targets to make the points he get be as much as possible. You can assume that Fat Brother is good at shooting when he is playing together with Maze, he can shoot any target as he wish.
Note that Fat Brother can choose arbitrarily number of targets to shoot.