时间限制： 1.0 秒

空间限制： 512 MB

题目背景

曙梦乐园即将举办周末特别企划——“亲子趣味问答”游园活动。作为活动策划，小梦手里有一份庞大的候选题库，她需要从中挑选出一套既能保证互动节奏，又能涵盖足够多乐园主题的题目组合。

题目描述

题库中共有 $n$ 道候选问答题，总共涉及 $k$ 个不同的乐园趣味主题（例如童话、探险、自然等知识点）。

其中第 $i$ 题涉及的主题集合为 $S_i$（保证 $S_i\subseteq\{1,2,\cdots,k\}$），准备该题（如布置互动道具）的工作量为 $a_i$。

为了保证活动的体验，小梦需要给出一种选题方案，并且必须满足以下限制：

1. 节奏限制：为了确保问答环节在游园手册上的分布均匀，$\forall~ 1\le i\le n-m+1$，满足连续的第 $i,i+1,\cdots i+m-1$ 题中至少有一道被选中；
2. 多样性限制：给定 $c$，保证最终的选题方案中，所有被选中的题目合起来至少包含 $c$ 个不同的趣味主题。

在此基础上，小梦希望准备活动的总工作量尽可能小。你只需要帮她计算出这个最小的总工作量。

输入格式

从标准输入读入数据。

第一行为四个正整数 $n,k,m,c$，分别表示候选题目数量、趣味主题总数、节奏限制中的区间长度、多样性限制中的主题数量下限。

接下来一行为 $n$ 个正整数 $a_1,\cdots a_n$，依次表示各题目的工作量。

接下来 $n$ 行，每行第一个正整数 $d_i$ 表示第 $i$ 题涉及的趣味主题数量（即 $|S_i|$）；之后跟随 $d_i$ 个正整数，为该题具体包含的主题编号，保证所有编号互异，且按照升序给出。

输出格式

输出到标准输出。

输出一行一个整数，表示满足所有限制的最佳选题方案的工作量最小值。特别地，若无法组成满足限制的选题方案，则输出 $-1$。

10 10 10 3
5 3 8 10 3 2 9 9 5 2
1 10
8 1 2 3 4 5 6 9 10
2 5 6
4 2 4 7 9
1 7
3 1 4 8
3 5 7 8
4 1 6 9 10
2 1 6
2 6 8

2

样例 1 解释

在本样例中，共有 $n=10$ 道题，趣味主题总数 $k=10$。

• 根据节奏限制，由于区间长度 $m=10$ 且 $n=10$，我们需要在第 $1 \sim 10$ 题中至少选择一道题。
• 根据多样性限制，由于 $c=3$，所选择的题目合起来包含的不同趣味主题数量总和必须至少为 3。

观察给出的各题工作量 $a_i$ 依次为：$5, 3, 8, 10, 3, 2, 9, 9, 5, 2$。

一种最优的选题方案是仅选择第 6 题：

• 第 6 题的工作量 $a_6 = 2$。
• 第 6 题包含的主题集合为 $S_6 = \{1, 4, 8\}$，共包含 3 个不同的趣味主题，满足了多样性限制（至少包含 $c=3$ 个主题）。
• 该方案总工作量为 2。

由于所有题目中最小的工作量就是 2，且根据限制我们至少需要选择 1 道题，因此总工作量不可能低于 2。所以满足条件的最小工作量即为 2。

子任务

对于所有数据，保证：

• $1\le m\le n\le 10^5$；
• $1\le d_i\le k\le 10^5$；
• $1\le c\le 3$；
• $1\le a_i\le 10^9$；
• $\sum\limits_{i=1}^n d_i\le 3\times 10^5$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。