# D. Pair of Topics

The next lecture in a high school requires two topics to be discussed. The i-th topic is interesting by ai units for the teacher and by bi units for the students.

The pair of topics i and j (i < j) is called good if ai + aj > bi + bj (i.e. it is more interesting for the teacher).

Your task is to find the number of good pairs of topics.

## Input

The first line of the input contains one integer n (2 ≤ n ≤ 2⋅105) — the number of topics.

The second line of the input contains n integers a1,a2,…,an (1 ≤ ai ≤ 109), where ai is the interestingness of the i-th topic for the teacher.

The third line of the input contains n integers b1,b2,…,bn (1 ≤ bi ≤ 109), where bi is the interestingness of the i-th topic for the students.

## Output

Print one integer — the number of good pairs of topic.

## Examples

input

5
4 8 2 6 2
4 5 4 1 3


output

7


input

4
1 3 2 4
1 3 2 4


output

0


## Problem solving

#include<bits/stdc++.h>
#define IOS()     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll N = 2e5+7;
ll a[N];
ll cmp(ll a,ll b)
{
return a>b;
}
inline void solve()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++)
{
ll x;cin>>x;
a[i]-=x;
}
sort(a,a+n,cmp);
ll ans = 0;
for(int i=0;i<n;i++)
{
if(a[i]<=0) break;

int l=i,r=n-1;

while(l<r)
{
int mid = (l+r+1)/2;

if(a[i]+a[mid]<=0) r=mid-1;
else l = mid;
}
ans += l-i;
}
cout<<ans<<endl;

}
int main()
{
IOS();
solve();
return 0;
}


# E. Sleeping Schedule

Vova had a pretty weird sleeping schedule. There are h hours in a day. Vova will sleep exactly n times. The ii-th time he will sleep exactly after ai hours from the time he woke up. You can assume that Vova woke up exactly at the beginning of this story (the initial time is 00). Each time Vova sleeps exactly one day (in other words, h hours).

Vova thinks that the ii-th sleeping time is good if he starts to sleep between hours l and r inclusive.

Vova can control himself and before the ii-th time can choose between two options: go to sleep after ai hours or after ai − 1 hours.

Your task is to say the maximum number of good sleeping times Vova can obtain if he acts optimally.

## Input

The first line of the input contains four integers n,h,l and r (1 ≤ n ≤ 2000,3 ≤ h ≤ 2000,0 ≤ l ≤ r < h) — the number of times Vova goes to sleep, the number of hours in a day and the segment of the good sleeping time.

The second line of the input contains n integers a1,a2,…,an(1 ≤ ai < h), where ai is the number of hours after which Vova goes to sleep the ii-th time.

## Output

Print one integer — the maximum number of good sleeping times Vova can obtain if he acts optimally.

## Example

input

7 24 21 23
16 17 14 20 20 11 22


output

3


DP 待补！