青色党（Party of Cyans）及其尊贵的国王 Alexey 决定在即将到来的 CodeForces 比赛中挑战 Gennady。第一组有 $n$ 名成员，编号从 $1$ 到 $n$；第二组有 $n$ 名成员，编号从 $n+1$ 到 $2n$。比赛中将会有 $m$ 道题目。

Alexey 将按如下方式分配题目：对于每一道题，Alexey 会指派第一组中的恰好一名成员和第二组中的恰好一名成员共同负责该题。之后，每位成员会在他被指派的题目中选择恰好一道题来完成。只有当两名成员都选择同一道题时，该题才会被视为已解决。

成员们会尽其所能，并始终最大化已解决题目的数量。

然而，青色党的成员不会免费解决题目。设 $c$ 为分配给成员 $i$ 的题目数量，则 Alexey 需要支付给该成员的报酬为 $p_{i,c}$。

根据比赛规则，Alexey 只有在团队解决的题目数量至少为 $l$ 且至多为 $r$ 时才能击败 Gennady。请帮助 Alexey 在支付给成员的报酬总额最小的情况下赢得比赛。

输入格式

第一行包含整数 $n, m, l$ 和 $r$：每组的成员人数、题目数量以及题目数量的下界和上界 ($1 \le n \le 30, 0 \le m \le 30, 0 \le l \le r \le n$)。

接下来的 $2 \cdot n$ 行包含每位成员的薪资要求：第 $i$ 行包含 $m+1$ 个整数 $p_{i,0}, p_{i,1}, \dots, p_{i,m}$ ($-10^9 \le p_{i,j} \le 10^9$)。

输出格式

如果无论如何支付都无法击败 Gennady，请在单行上输出 “DEFEAT”。

否则，在第一行输出一个整数：使 Alexey 赢得比赛所需的最小总报酬。之后，再输出 $m$ 行。第 $i$ 行输出两个整数 $a_i$ 和 $b_i$，其中 $a_i$ 是分配给第 $i$ 道题的第一组成员编号，$b_i$ 是分配给第 $i$ 道题的第二组成员编号。

如果有多种可能的方案，输出其中任意一种即可。

样例

样例输入 1

2 0 2 2
8
9
3
4

样例输出 1

DEFEAT

样例输入 2

2 8 2 2
2 5 5 10 -10 -1 3 5 9
8 -10 9 9 0 1 -3 1 -1
0 5 -1 5 3 -9 1 10 6
5 -4 8 -2 2 -8 6 3 -3

样例输出 2

-21
1 3
2 4
1 3
1 3
1 3
2 3
2 4
2 4

样例输入 3

3 5 2 3
100 75 125 150 175 200
125 100 75 100 125 150
225 200 175 200 225 250
225 200 175 200 225 250
125 100 75 100 125 150
100 75 125 150 175 200

样例输出 3

650
1 4
2 5
3 6
2 4
3 5