Inns and Coffee Shops Selection

There are \(n\) unique inns along the Lijiang River, numbered from \(1\) to \(n\). Each inn is decorated in one of \(k\) color tones, represented by integers from \(0\) to \(k-1\), and every inn has a coffee shop with its own minimum consumption requirement.

Two travelers, who share the same favorite color tone, wish to experience two different inns of that tone. They decide to book two distinct inns that have the same color tone. Later in the evening, they plan to meet at one of the coffee shops located between (and including) the two inns they have chosen. However, they require that the coffee shop’s minimum consumption does not exceed \(p\).

Your task is to calculate the number of ways to choose two inns (with the same color tone) such that there exists at least one coffee shop in the interval between them (including the two inns) with a minimum consumption \(\le p\).

The existence condition for a chosen pair of inns at positions \(i\) and \(j\) (with \(i 0. \]

inputFormat

The first line contains three integers \(n\), \(k\) and \(p\) --- the number of inns, the number of color tones, and the consumption limit for the coffee shop, respectively.

The second line contains \(n\) integers: the \(i\)-th integer represents the color tone of the \(i\)-th inn (an integer between \(0\) and \(k-1\)).

The third line contains \(n\) integers: the \(i\)-th integer represents the minimum consumption of the coffee shop at the \(i\)-th inn.

outputFormat

Output a single integer: the total number of valid pairs of inns where the two travelers can stay and later meet at a coffee shop having a minimum consumption \(\le p\) located between them.

sample

5 3 10
0 1 0 0 2
12 5 9 11 10

3