该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

2025 年 12 月 31 日深夜，跨年烟火已经点亮夜空。为了迎接 2026 年元旦的第一声钟响，“九老师”搭建了一条环形的灯会长廊：长廊绕成一圈，首尾相接，像一条不断循环的年轮。

长廊的左侧入口摆着“旧年”的灯笼阵列，右侧出口摆着“新年”的灯笼阵列。两边之间有无数条灯线连接，每条灯线都有两种属性：

• 断开代价：剪断这条灯线需要消耗多少能量；
• 相位极性：这条灯线是否带有“新年相位”（0/1）。

为了让“旧年”与“新年”彻底隔开，九老师必须剪断一些灯线。但元旦的仪式要求非常讲究：被剪断的“新年相位”灯线（相位为 1）的数量必须恰好为奇数，这样才能让新年的第一束烟火在灯廊中共鸣。

题目描述

给定一个 $N\times M$ 的无向网格图，顶点为 $(i,j)$（$1\le i\le N,\,1\le j\le M$），边分两类：

• 横向边：$(i,j)\leftrightarrow(i,j+1)$（$1\le j<M$）
• 纵向边（循环）：$(i,j)\leftrightarrow(i+1,j)$（$1\le i<N$），并且 $(N,j)\leftrightarrow(1,j)$ 也存在

每条边 $e$ 有权值 $W_e$ 与相位 $P_e\in\{0,1\}$。

定义

• $S=\{(i,1)\mid 1\le i\le N\}$（第 1 列，旧年入口）
• $T=\{(i,M)\mid 1\le i\le N\}$（第 $M$ 列，新年出口）

你需要构造一个顶点划分 $(V_S,V_T)$，满足：

1. 边界归属：$S\subseteq V_S$，$T\subseteq V_T$，且 $V_S\cap V_T=\varnothing$，$V_S\cup V_T=V$；

2. 设割集

   $$E_{cut}=\{(u,v)\in E\mid u\in V_S,\,v\in V_T\},$$

   要求 $E_{cut}$ 中满足 $P_e=1$ 的边条数恰好为奇数；

3. 最小化

   $$\sum_{e\in E_{cut}} W_e.$$

若不存在满足条件的划分，输出 $-1$。

输入格式

第一行两个整数 $N,M$。

接下来输入所有横向边信息：

• 共 $N$ 行，每行 $M-1$ 对整数 $(W,P)$

• 第 $i$ 行第 $j$ 对描述边 $(i,j)\leftrightarrow(i,j+1)$

再接下来输入所有纵向边信息（含循环边）：

• 共 $N$ 行，每行 $M$ 对整数 $(W,P)$

• 第 $i$ 行第 $j$ 对描述边 $(i,j)\leftrightarrow(i+1,j)$，其中 $i=N$ 时表示 $(N,j)\leftrightarrow(1,j)$

注意： 诱导子图 ($G[V_S]$) 与 ($G[V_T]$) 必须均为连通图。

输出格式

输出一个整数，表示满足条件的最小总代价；若无解输出 $-1$。

3 3
1 0 1 1
1 0 1 0
1 0 1 0
100 0 100 0 100 0
100 0 100 0 100 0
100 0 100 0 100 0

3

3 3
1 0  1 0
1 0  1 0
1 0  1 0
100 0 100 0 100 0
100 0 100 0 100 0
100 0 100 0 100 0

-1

数据范围

对于 $10\%$ 的数据，满足 $N\cdot M\le 20$。

对于另 $20\%$ 的数据，满足 $\min(N,M)\le 15$，且 $N,M\le 120$。

对于 $100\%$ 的数据，满足 $3\le N,M\le 120$，$1\le W\le 10^9$，$P\in\{0,1\}$。