Pairs under a limit

Problem

A courier can carry two parcels if their weights add up to less than a limit. Count the pairs of parcels (different positions in the list) whose total weight is less than the limit.

Input, output and limits

Input: Line 1: the weights, separated by spaces, in any order. Line 2: the limit.
Output: One integer: the number of pairs.
Constraints: 2 ≤ number of parcels ≤ 100000
1 ≤ each weight and the limit ≤ 1000000000

Examples

Example

Input

40 10 25 5 30
45

Output

Pairs: 5+10, 5+25, 5+30, 10+25, 10+30.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Sort the weights first. After sorting, two pointers can count many pairs at once.

Hint 2

If the smallest and the largest at the pointers fit, then the smallest also fits with every weight between them.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Container with the most watermedium
Closest pair of costsmedium
Merge two sorted listseasy
Sort the three levelsmedium
Sorted squareseasy

All Python problems

Problem

Input, output and limits

Examples

Hints

More Two Pointers problems

Problem

Input, output and limits

Examples

Hints

More Two Pointers problems