問題文
迅速成长中的K公司,由于高节奏的采用,座位已经不够了。
下一处办公室的搬迁地点已经决定了,但由于一些成人的原因,决定扩大现有办公室。
由于办公室变大了,所以需要更换。
K公司非常忙碌,所以不想在换座位上花费太多时间。
您必须使用手推车更换座位。
将行李放在推车上的座位上
花了 5 分钟才把行李从车上卸下到座位上。
需要 5 分钟。
1 购物车有 1 只能携带一个人的行李。
此时,从您开始装载推车到您卸完为止,均视为推车装载有行李,您不能在上面放置其他人的行李。
如果您要前往的座位上有行李,您将无法卸下它。
此时,假设座位上有行李,直到座位上的行李已经装到推车上。
此外,即使您没有换座位,也可以暂时将行李卸下到没有行李的座位上,但不能将多人的行李放在一个座位上。
根据换座前后的座位表以及推车数量,计算换座所需的最短时间。
推车的性能非常好,装完行李后应该不会花很长时间就可以移动到目的地座位。
入力
N M L
a_{1} b_{1}
:
a_{L} b_{L}
- 输入是 L+1 。
- 第一行表示座位数。 N ( 1 \leq N \leq 30 )和 代表购物车的数量 M ( 1 \leq M \leq N )和 代表员工人数 L ( 1 \leq L \leq N 和 L \leq 15 ) 用空格分隔。 在
- 从第二行开始 L 行包含 i ( 1 \leq i \leq L ) 换座前的第号员工座位号 a_{i} ( 1 \leq a_{i} \leq N ) 以及换座后的座位号 b_{i} ( 1 \leq b_{i} \leq N ) 用空格分隔。 在
- i \neq j 如果 a_i \neq a_j 。
- i \neq j 如果 b_i \neq b_j 。
部分点
出力
如果无法更换座位,
-1 。请注意,行尾需要换行。 定义
入力例 1
3 3 3 1 2 2 3 3 1
出力例 1
10
- 开始换座位时,开始将三人的行李装载到三辆推车上。
- 开始换座位五分钟后,我们开始把三个人的行李卸到各自的目的地。
- 通过以上步骤,10分钟内即可完成换座。
入力例 2
3 2 3 1 2 2 3 3 1
出力例 2
20
- 更换座位的示例如下所示。
- 当您开始更换座位时,开始将 1 号和 2 号座位的行李装载到购物车上。
- 换座开始五分钟后,1号座位上的行李开始从车上卸载到2号座位。
- 换座开始10分钟后,3号座位的行李开始装上车。
- 换座开始15分钟后,两人开始将行李卸到推车上前往各自的目的地。
- 通过以上步骤,20分钟内即可完成换座。
入力例 3
3 1 3 1 2 2 3 3 1
出力例 3
-1
- 在这种情况下,无法更换座位。
入力例 4
4 1 3 1 2 2 3 3 1
出力例 4
40
- 在这种情况下,您可以在 40 分钟内使用空座位更换座位。