How to efficiently code Dynamic Time Warping algorithm with a locality constrain?

Question

For given two lists $[s_1, s_2, ... s_n]$ and $[t_1, t_2, ..., t_m]$

I need to implement DTW algorithm with one extra constraint:

If $s_i$ is matched with $t_j$ then the next element $s_{i+1}$ has to be matched with some $t_{j+k}$ close enough to $t_j$ (i.e. $0 \le k \le W$ for some fixed window size $W$).

This constraint has to hold for each $s_i$.

1) Does there exist $O(nm)$ solution to such problem?

2) If an efficient algorithm does not exist, what would be a good practical solution?

(Note that locality constraint mentioned in the DTW link above is different from the constraint I need).