132. Patching Array

Given a sorted array nums and integer n, return the minimum number of patches (elements to add) so that every integer in [1,n] can be formed as a sum of some subset. Input: '[nums], n'.

Input: '[nums], n'.

Output: Integer — minimum patches.

Examples

Input: [1,3], 6
Output: 1
Explanation: Add 2 to cover all of [1,6].

Input: [1,5,10], 20
Output: 2
Explanation: Two patches needed.

Input: [1,2,2], 5
Output: 0
Explanation: Already covers [1,5].

Constraints

• 1<=nums.length<=1000
• 1<=nums[i]<=10^4
• 1<=n<=2^31-1

Asked by