Infosys Online Assessment Round

Bob is playing his favorite game! Its a game of mystery which requires a lot of experience in multiple aspects and obviously, he's got what it takes!

Formally speaking, the game can be described in following way:
  - The game is played on an N*M 2D map
  - Bob starts the game at the cell denoted as 'X' on the map
  - Bob can travel through the map one cell at a time in the following directions UP, DOWN, LEFT, RIGHT
  - Bob cannot go off the map
  - Empty cell is denoted by '.'
  - There are some keys located on the map denoted as 'K'
  - Bob can visit the cells which have the keys and collect them
  - The goal of the game is to reach the door and open at cell denoted as 'O'
  - The door wont open unless u have all the keys were collected.

Notes:
  - Bob can go through a cell which contains a key and not pick it up (this affects the number of valid paths).
  - There might be zero keys on the map
  - Since the answer can be large, return it modulo(10^9 + 7)

Input Format:
First line contains N, number of rows
Next line contains M, number of columns
Each line i of the N subsequent lines contains a string describing map

Output Format:
Return the number of shortest unique paths to achieve goal

Constraints:
1 <= N <= 20
1 <= M <= 20
M <= len(map[i]) <= M

Sample Input:
1
5
X . O . K

Sample Output:
1

Explanation:
There is only 1 optimal path -> RRRRPLL, where P is picking key

Sample Input:
2
2
X K
0 .

Sample Output:
2

Explanation:
There are 2 optimal paths -> RPLD and RPDL

Given N intervals, such than the ith interval covers the range from L[i] to R[i] both inclusive.

The intersection of several intervals is the range that is covered by all the intervals. Example, if the intersection of intervals (2,5) and (3,6) and (1,7) is (3,5) and the length of the intersection is 3 since it covers three points (3,4,5).

Your task is to find the maximum length of the intersection that can be obtained by choosing ** exactly M intervals ** out of given N intervals.

Input Format:
First line contains integer N, denoting number of intervals.
Next line contains integer M, denoting number of intervals you should choose.
Next N lines are of subsequent lines containing L[i].
Next N lines are of subsequent lines containing R[i].

Output Format:
Return maximum length of the intersection of M intervals.
If the intersection is empty return 0;

Constraints:
1 <= N <= 10^5
1 <= M <= N
1 <= L[i] <= 10^6
L[i] <= R[i] <= 10^6

Sample Input:
3
2
1
2
5
4
6
7

Sample Output:
3

Explanation:
N = 3, M = 2
L = [1, 2, 5]
R = [4, 6, 7]

It is optimum to choose the first and second intervals, as their intersection is (2,4) and its length is 3