## A. Maximum Increase

You are given array consisting of n integers. Your task is to find the maximum length of an increasing subarray of the given array.

A subarray is the sequence of consecutive elements of the array. Subarray is called increasing if each element of this subarray strictly greater than previous.

### Input

The first line contains single positive integer n ($1 \leq n \leq 10^5$) — the number of integers.

The second line contains n positive integers $a_1$, $a_2$, …, $a_n$ ($1 \leq a_i \leq 10^9$).

### OutPut

Print the maximum length of an increasing subarray of the given array.

### Examples

input
5
1 7 2 11 15
output
3

input
6
100 100 100 100 100 100
output
1

input
3
1 2 3
output
3


## B. Powers of Two

You are given n integers $a_1$, $a_2$, …, $a_n$. Find the number of pairs of indexes i, j (i < j) that $a_i + a_j$ is a power of 2 (i. e. some integer x exists so that $a_i + a_j = 2^x$).

### Input

The first line contains the single positive integer n ($1 \leq n \leq 10^5$) — the number of integers.

The second line contains n positive integers $a_1$, $a_2$, …, $a_n$ ($1 \leq a_i \leq 10^9$).

### Output

Print the number of pairs of indexes i, j (i < j) that $a_i$ + $a_j$ is a power of 2.

### Examples

input
4
7 3 2 1
output
2

input
3
1 1 1
output
3


## C. Cellular Network

You are given n points on the straight line — the positions (x-coordinates) of the cities and m points on the same line — the positions (x-coordinates) of the cellular towers. All towers work in the same way — they provide cellular network for all cities, which are located at the distance which is no more than r from this tower.

Your task is to find minimal r that each city has been provided by cellular network, i.e. for each city there is at least one cellular tower at the distance which is no more than r.

If r = 0 then a tower provides cellular network only for the point where it is located. One tower can provide cellular network for any number of cities, but all these cities must be at the distance which is no more than r from this tower.

### Input

The first line contains two positive integers n and m ($1 \leq n,m \leq 10^5$) — the number of cities and the number of cellular towers.

The second line contains a sequence of n integers a1, a2, …, an ($-10^9 \leq a_i \leq 10^9$) — the coordinates of cities. It is allowed that there are any number of cities in the same point. All coordinates ai are given in non-decreasing order.

The third line contains a sequence of m integers b1, b2, …, bm ($-10^9 \leq a_i \leq 10^9$) — the coordinates of cellular towers. It is allowed that there are any number of towers in the same point. All coordinates bj are given in non-decreasing order.

### Output

Print minimal r so that each city will be covered by cellular network.

### Examples

input
3 2
-2 2 4
-3 0
output
4

input
5 3
1 5 10 14 17
4 11 15
output
3


## D. Road to Post Office

Vasiliy has a car and he wants to get from home to the post office. The distance which he needs to pass equals to d kilometers.

Vasiliy’s car is not new — it breaks after driven every k kilometers and Vasiliy needs t seconds to repair it. After repairing his car Vasiliy can drive again (but after k kilometers it will break again, and so on). In the beginning of the trip the car is just from repair station.

To drive one kilometer on car Vasiliy spends a seconds, to walk one kilometer on foot he needs b seconds (a < b).

Your task is to find minimal time after which Vasiliy will be able to reach the post office. Consider that in every moment of time Vasiliy can left his car and start to go on foot.

### Input

The first line contains 5 positive integers d, k, a, b, t ($1 \leq d \leq 10^12$; $1 \leq k, a, b, t \leq 10^6$ ; a < b), where:

d — the distance from home to the post office;
k — the distance, which car is able to drive before breaking;
a — the time, which Vasiliy spends to drive 1 kilometer on his car;
b — the time, which Vasiliy spends to walk 1 kilometer on foot;
t — the time, which Vasiliy spends to repair his car.

### Output

Print the minimal time after which Vasiliy will be able to reach the post office.

### Examples

input
5 2 1 4 10
output
14

input
5 2 1 4 5
output
13


### 题解

$1 \leq d \leq 10^12$; $1 \leq k, a, b, t \leq 10^6$ ; a < b