U461237 「P1220 关路灯」加强版
题目背景
卡掉了原题错误的爆搜。
期望时间复杂度：$O(n^2)$.
注：因造数据失误，可能会有 $w=0$ 的情况，若对您的做法有影响请注意特判。
题目描述
同 [P1220](https://www.luogu.com.cn/problem/P1220)。
输入格式
同 [P1220](https://www.luogu.com.cn/problem/P1220)。
输出格式
同 [P1220](https://www.luogu.com.cn/problem/P1220)。
说明/提示
数据范围：
除 $n$ 外均不变。$n$ 的改动如下：
- 对于前 $10\%$ 的测试点，$1\le n\le10$。
- 对于前 $50\%$ 的测试点，$1\le n\le200$。
- 对于所有测试点，$1\le n\le5\times10^3$。