Inn Accommodation and Coffee Shop Selection

There are \(n\) inns along the bank of the Lijiang river, numbered from \(1\) to \(n\) in order. Each inn is decorated in one of \(k\) shades (represented by integers \(0\) to \(k-1\)), and every inn has its own café with a specified minimum consumption value.

Two travelers, who both favor the same shade, plan to experience two different inns decorated in that shade. They book two different inns with the same tone. In the evening, they choose a café located between the two inns (including the inns they are staying in) where the minimum consumption does not exceed \(p\) yuan.

Please count the total number of lodging pairs (i.e. pairs of distinct inns with the same tone) such that there is at least one café between them (inclusive) with a minimum consumption \(\le p\).

More formally, let the tone of the \(i\)-th inn be \(a_i\) and the café's minimum consumption be \(b_i\) for \(1 \le i \le n\). You want to count the number of pairs \((i, j)\) where \(1 \le i < j \le n\), \(a_i = a_j\), and \(\min\{b_i, b_{i+1}, \dots, b_j\} \le p\).

inputFormat

The first line contains three integers \(n\), \(k\), and \(p\) \((1 \le n \le 10^5,\ 1 \le k \le n)\).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) where each \(a_i\) is in the range \([0, k-1]\) representing the tone of the \(i\)-th inn.

The third line contains \(n\) integers \(b_1, b_2, \dots, b_n\) representing the minimum consumption at the café in the \(i\)-th inn.

outputFormat

Output a single integer representing the number of ways to choose two inns (with the same tone) such that there is at least one café between them (inclusive) with a minimum consumption \(\le p\).

sample

5 3 4
0 1 0 2 0
6 3 5 2 4

3