A. Sticker Album
time limit per test
0.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There's a sticker album very popular among the children of Pavussulandia. To fill the album, they need to find $$$M$$$ distinct stickers with identifiers from $$$1$$$ to $$$M$$$. The stickers are sold in packs, and there are $$$N$$$ packs available for purchase. Each pack $$$i$$$, such that $$$1 \leq i \leq N$$$, has $$$K_i$$$ stickers and costs $$$V_i$$$ reais.

In the store, the stickers are arranged on a shelf in order, and you have to choose an interval $$$[i, j]$$$ and buy all the packs from $$$i$$$ to $$$j$$$ (including $$$i$$$ and $$$j$$$). Since the stickers are highly sought after, you can only make one interval choice.

Little Biel is excited to fill his album; however, his family doesn't have much money. With that, he needs your help to spend as little as possible and complete the album. If there is no answer, you must inform Biel, preventing him from unnecessarily wasting money.

Input

The first line contains the integers $$$N$$$ and $$$M$$$ $$$(1 \leq N,M \leq 2 \cdot 10^5)$$$, where $$$N$$$ is the number of packs and $$$M$$$ is the number of distinct stickers.

The next $$$N$$$ lines are formatted as:

$$$K_i \quad V_i \quad F_{i,1} \quad F_{i,2} \quad \dots \quad F_{i,K_i}$$$

Where $$$K_i$$$ $$$(1 \leq K_i \leq M)$$$ is the number of stickers in pack $$$i$$$ $$$(1 \leq i \leq N)$$$, $$$V_i$$$ $$$(1 \leq V_i \leq 10^9)$$$ is the price of pack $$$i$$$, and $$$F_{i,j}$$$ $$$(1 \leq F_{i,j} \leq M)$$$ is the identifier of the sticker.

Note that the same pack may contain duplicate stickers. And it's guaranteed that the sum of all the $$$K_i$$$ quantities of stickers from all the $$$N$$$ packs does not exceed $$$2 \cdot 10^5$$$.

Output

Your program should print $$$-1$$$ if there is no valid interval. If there is, print two lines. The first one with the minimum total spent and the second with the values $$$i$$$ and $$$j$$$ of the chosen interval. In the event of multiple answers, print any of them.

Examples
Input
4 5
1 2 5
2 4 1 5
3 5 4 2 1
2 1 3 1
Output
10
2 4
Input
4 5
1 1 5
2 1 1 5
2 1 2 1
2 1 3 1
Output
-1
Input
1 4
4 10 1 2 3 4
Output
10
1 1
Note

In the first example, we have $$$5$$$ distinct stickers (numbered from $$$1$$$ to $$$5$$$) and the following packs:

  • Pack $$$1$$$ costs $$$2$$$ and contains sticker number $$$5$$$.
  • Pack $$$2$$$ costs $$$4$$$ and contains sticker numbers $$$1$$$ and $$$5$$$.
  • Pack $$$3$$$ costs $$$5$$$ and contains sticker numbers $$$4$$$, $$$2$$$, and $$$1$$$.
  • Pack $$$4$$$ costs $$$1$$$ and contains sticker numbers $$$3$$$ and $$$1$$$.

With the choice of packs in the interval $$$[2,4]$$$, Biel will pay a total of $$$4 + 5 + 1 = 10$$$ and will obtain all $$$5$$$ stickers. It can be shown that this is the least expensive choice to obtain all the stickers.