Boat

Interview

Time limit1sMemory limit2048 MB

Summary

Find the fewest boat crossings needed to ferry all residents across the river, where the boat carries at most two people within a weight limit.

Level: Medium4 of 10
Topics: Greedy, Two pointers, Sorting
Solved: No attempts yet

Problem

A river separates Upper Barareh from Lower Barareh. A two-seater boat, which can carry at most two people up to a fixed weight capacity, is provided to transport people between the two towns. The boat must be steered by at least one person, so it cannot cross the river without passengers.

The National Barareh Festival is held in Upper Barareh. Every resident of Lower Barareh wants to attend and must move to Upper Barareh as quickly as possible. Your task is to move all of them to Upper Barareh using the fewest boat trips across the river.

Input

The first line contains two integers $n$ and $w$ . Here $n$ is the number of Lower Barareh residents ( $1 \le n \le 1000$ ), and $w$ is the maximum weight the boat can carry ( $1 \le w \le 10^6$ ).

The next line contains $n$ space-separated integers, the weights of the Lower Barareh residents. Every weight is a positive integer not exceeding $10^6$ .

Output

If it is impossible to move all the residents, print -1. Otherwise, print the minimum number of times the boat must cross the river, in either direction, to move every Lower Barareh resident to Upper Barareh.

Examples2

Example 1
Input
```
3 7
1 3 4
```
Expected output
```
3
```
Example 2
Input
```
3 4
2 3 4
```
Expected output
```
-1
```