在藍橋王國，國王統(tǒng)治著一支由 n 個小隊組成的強大軍隊。每個小隊都由相同職業(yè)的士兵組成。具體地，第 i 個小隊包含了 bi 名職業(yè)為 ai 的士兵。

近日，國王計劃在王宮廣場舉行一場盛大的士兵檢閱儀式，以慶祝王國的繁榮昌盛。然而，在士兵們入場的過程中，一場突如其來的風暴打亂了他們的行列，使得不同小隊的士兵混雜在一起，次序亂成一團，

盡管國王無法知道每個士兵的具體職業(yè)，但為了確保儀式能順利進行，國王打算從這些混亂的士兵中選出一部分，組成 k 個“純職業(yè)小組”進行檢閱。一個“純職業(yè)小組”定義為由 3 名同職業(yè)的士兵組成的隊伍。

請問，國王至少需要選擇多少名士兵，才能確保這些士兵可以組成 k 個“純職業(yè)小組”。

輸入的第一行包含一個整數 T，表示每次輸入包含 T 組數據。

接下來依次描述 T 組數據。每組數據的第一行包含兩個整數 nt 和 k ，用一個空格分隔，表示小隊的數量和要組成的純職業(yè)小組的數量。

接下來的 nt 行，每行包含兩個整數 ai 和 bi ，用一個空格分隔，表示第 i個小隊中士兵的職業(yè)和數量。

輸出 T 行，每行包含一個整數，依次表示每組數據的答案，即為了組成 k個“純職業(yè)小組”，國王至少需要選擇的士兵數量。

如果無論如何也無法組成 k個“純職業(yè)小組”，則輸出 ?1。

2
3 2
1 3
2 3
3 3
3 5
1 3
2 3
3 3

8
-1

【樣例說明】

在第一個樣例中，要想組成 2 個“純職業(yè)小組”，國王至少需要選擇 8 名士兵。若只選擇了 7 名士兵，則這 7 名士兵的職業(yè)可能為 1, 1, 1, 2, 2, 3, 3，無法組成 2 個“純職業(yè)小組”。

在第二個樣例中，即使選擇了所有士兵，也無法組成 5 個“純職業(yè)小組”，因此輸出 ?1。