664. Maximum Score From Multiplication Operations

Given arrays nums and multipliers, perform m = len(multipliers) operations. In the i-th operation you take multipliers[i] times either the first or last remaining element of nums, add it to your score, and remove that element. Return the maximum total score. The input is JSON {nums, multipliers}.

Input: JSON {nums, multipliers}.

Output: Integer — the maximum score.

Examples

Input: {"nums":[1,2,3],"multipliers":[3,2,1]}
Output: 14
Explanation: 3*3 + 2*2 + 1*1 = 14.

Input: {"nums":[-5,-3,-3,-2,7,1],"multipliers":[-10,-5,3,4,6]}
Output: 102
Explanation: Optimal end choices.

Input: {"nums":[1,2,3],"multipliers":[1]}
Output: 3
Explanation: Take the last once.

Constraints

• 1<=m<=n<=1000

Asked by