F - Sliding

問題

容量 $N$ の 💩 があります。また、横一列に $M$ 個のマス目が並んでいます。
左から $i$ 番目のマスには、種類 $I_i$ 、栄養 $S_i$ の食べ物が落ちています。

今、 💩 は、あるマスからあるマスまでの範囲にある食べ物を全て食べようとしています。しかし、💩 はその容量である $N$ 種類の食べ物を摂取すると死にます。
💩 が死ぬような範囲の選び方のうち、最も摂取した栄養の合計が小さくなるような選び方はどこですか？

制約

• $1 \leq N \leq M \leq 400000$
• $1 \leq I_i \leq M \; (1 \leq i \leq M)$
• $1 \leq S_i \leq 10^9 \; (1 \leq i \leq M)$

小課題

1. (100点) $1 \leq N \leq M \leq 1000$
2. (50点) 追加の制約はない。

入力

$N~M$

$I_1~I_2~...~I_M$

$S_1~S_2~...~S_M$

出力

最適な範囲を 「 $L \leq i < R$ を満たす $i$ が表す範囲（つまり、左から $L$ 番目から $R-1$ 番目までの範囲）」 としたときの $L, R$ を空白区切りで出力してください。
最適な範囲が複数ある場合は、 $L$ が最小になるものを出力してください。
また、どのような範囲を選んでも 💩 が死なない場合は

$-1~-1$

と出力してください。

入出力例

入力例 1

3 5
1 3 2 3 1
4 1 3 5 2
Copy

出力例 1

1 4
Copy

この範囲を選ぶと３種類を摂取することになり、💩は死にます。そのような範囲の選び方で最適なのは $[1, 4)$ の範囲です。

入力例 2

4 10
1 2 2 4 3 1 1 3 2 4
3 1 3 5 2 9 1 2 5 6
Copy

出力例 2

1 6
Copy

入力例 3

4 5
1 2 3 3 1
1 1 1 1 1
Copy

出力例 3

-1 -1
Copy

この場合、💩は死にません。