'Coding has over 700 languages', '67% of programming jobs aren’t in the
technology industry', 'Coding is behind almost everything that is powered
by electricity'

Topics

There are 'N' students in a class, where 'N is odd'. The 'ith' student wants their marks to be in the range 'L[i]' to 'R[i]' (both inclusive). The teacher can give a total of at most 'X' marks to students. To show that the result is good, the teacher wants the median marks to be as large as possible.

Return the maximum median marks the teacher can obtain provided they optimally distribute the 'X' marks among students satisfying the ranges.

To find the median of a sequence of odd length, you have to sort it and take the element in the middle position after sorting.

It is guaranteed that the teacher has enough marks to give, i.e. L[1]+L[2]+.....+L[N] <= 'X'.

```
Let 'N' = 3, 'X' = 13, 'L' = [2, 3, 5], 'R' = [4, 5, 7].
We can assign 2 marks to the first student, 5 marks to the second student, and 5 marks to the third student.
So the median mark is 5 which is the maximum possible.
```

Detailed explanation

```
1 <= 'T' <= 10
1 <= 'N' <= 10^5
1 <= 'L[i]' <= 'R[i]' <= 10^5
1 <= 'X' <= 10^8
'N' is odd.
The Sum of 'N' overall test cases does not exceed 10^5.
Time Limit: 1 sec
```

```
2
3 26
10 1 4
12 4 11
1 15
2
9
```

```
11
9
```

```
First test case:-
We can assign 12 marks to the first student, 2 marks to the second student, and 11 marks to the third student.
So the median mark is 11 which is the maximum possible.
Second test case:-
We can assign 9 marks to the first student.
So the median mark is 9 which is the maximum possible.
```

```
2
5 26
4 2 2 6 5
4 4 7 8 6
1 5
4
7
```

```
6
5
```