Maximum Pair Sum Below Threshold

Easy

You are given an array of positive integers nums and an integer threshold . Your task is to find two distinct elements from the array (at indices i and j where i < j) such that their sum is strictly less than the threshold, and this sum is the maximum possible among all such valid pairs. Return the maximum sum that satisfies these conditions. If no such pair exists where the sum is strictly less than the threshold, return -1 . Key Observations: You must select exactly two different elements (by index), meaning you cannot use the same element twice. The sum must be strictly less than the threshold (not equal to or greater than). Among all valid pairs, you want the one with the largest possible sum that still respects the constraint.

Example 1

Input

nums = [34,23,1,24,75,33,54,8]
threshold = 60

Output

Explanation

We can choose the elements 34 and 24. Their sum is 34 + 24 = 58, which is strictly less than 60. No other valid pair produces a larger sum below the threshold. For instance, 34 + 33 = 67 exceeds the threshold, so it's invalid.

Example 2

Input

nums = [10,20,30]
threshold = 15

Output

-1

Explanation

The smallest possible pair sum is 10 + 20 = 30, which is not less than 15. Even the minimum pair exceeds the threshold, so no valid pair exists. We return -1.

Example 3

Input

nums = [5,8,3,2,10]
threshold = 12

Output

Explanation

The pair (5, 3) produces sum 8, and the pair (8, 3) produces sum 11. Since 11 < 12 and is the maximum valid sum, we return 11. Note that 8 + 5 = 13 exceeds the threshold and is invalid.

Constraints

1 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 1000
1 ≤ threshold ≤ 2000