Minimum Add to Make Parentheses Valid

A parentheses string is valid if it is empty, can be written as AB where A and B are valid strings, or can be written as (A) where A is a valid string. Given a parentheses string s, determine the minimum number of moves required to make s valid by inserting parentheses at any position.

Constraints

• 1 <= s.length <= 1000
• s[i] is either '(' or ')'.