A football team is planning its tactics for
For each match, the coach can choose one of two tactics: attacking or defensive.
If the team plays attacking in match
If the team plays defensive in match
The coach can choose attacking tactic in at most
Also, the team cannot play attacking tactic in three consecutive matches because the players will become too tired.
Your task is to find the maximum total morale points the team can gain after all matches.
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of matches and the maximum number of attacking matches allowed.
The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — morale points for playing attacking tactic.
The third line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — morale points for playing defensive tactic.
Print a single integer — the maximum total morale points possible.
Input
4 2
8 7 6 10
5 3 9 130One optimal plan is attacking in matches KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, and defensive in matches KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
The total morale is KaTeX can only parse string typed expression.
Example 2:
Input
3 3
10 10 10
1 1 121The team cannot attack in all three matches because three consecutive attacking matches are not allowed.
The best option is to attack in two matches and defend in one match, giving total morale KaTeX can only parse string typed expression.