Bài tập

Sau khi tham gia trò chơi "Bốc số", An tiếp tục tham gia trò chơi "Xếp gạch". Ban tổ chức cho trước một chồng gạch được xếp thành một hàng ngang và đánh số từ \(1\) đến \(n\). Số viên gạch ở các chồng lần lượt là \(a_1, a_2, \ldots, a_n\).

An cần thực hiện \(m\) lượt chơi tương ứng với dãy số nguyên dương \(b_1, b_2, \ldots, b_m\) đã biết trước. Ở lượt thứ \(i\) (\(1 \le i \le m\)), An được quyền thực hiện chỉ một trong hai lựa chọn:

• Bỏ qua không sử dụng giá trị \(b_i\).
• Xếp thêm \(b_i\) viên gạch lên chồng gạch thứ \(j\) (\(1 \le j \le n\)) nếu tất cả các chồng gạch thứ \(j, j+1, j+2, \ldots, n\) chưa từng được xếp thêm viên gạch nào trong các lượt trước đó.

Trò chơi dừng lại khi hết lượt hoặc An đã thực hiện xếp thêm gạch ở chồng thứ \(n\). Khi đó ban tổ chức sẽ đếm số gạch ở mỗi chồng và lấy số gạch ở chồng ít nhất làm điểm số của An.

Yêu cầu
Hãy tìm ra số điểm An đạt được.

Input

Nhập từ tệp B3.INP gồm 3 dòng:

• Dòng 1: Ghi hai số nguyên dương \(n\) và \(m\).
• Dòng 2: Ghi \(n\) số nguyên không âm \(a_1, a_2, \ldots, a_n\) (\(a_i \le 10^8\)).
• Dòng 3: Ghi \(m\) số nguyên dương \(b_1, b_2, \ldots, b_m\) (\(b_i \le 10^8\)).

Output

Ghi ra tệp B3.OUT gồm 1 dòng chứa số điểm An đạt được.

Example

5 3
2 5 1 4 6
1 3 4

4

Scoring

• \(40\%\) số test thỏa mãn \(m = 1\), \(1 \le n \le 10^3\).
• \(30\%\) số test thỏa mãn \(m = 2\) và \(10^3 < n \le 10^4\).
• \(30\%\) số test thỏa mãn \(10^4 < n, m \le 10^6\).

Không biết cụm từ "Làng đại học" có từ khi nào, bắt nguồn từ đâu, nhưng suốt những năm tháng đại học, chúng tôi đã thuộc nó làu làu, xem như một mật ngữ riêng của giới sinh viên TPHCM.

Những con đường rợp hoa giấy dẫn vào trường, bờ Hồ Đá và tán cây hoa chuông nhuộm vàng cả một vùng trời… đã trở thành chốn hẹn hò bí mật của bao cặp đôi ở độ tuổi đang yêu.

Nói không ngoa khi đã là sinh viên TPHCM, chẳng ai không biết đến "Làng đại học". Mật ngữ ấy như phần ký ức tươi đẹp theo suốt năm tháng đầu tiên đứa học sinh tỉnh lẻ bước chân lên Sài Gòn nhưng sợ sự xô bồ, tấp nập nơi thành phố. Ấy vậy, sau này ra trường, đi làm, lập gia đình, nhưng mỗi lần nhìn lại, bao kỷ niệm thanh xuân bỗng chốc ùa về trong veo.

Ấn tượng của riêng tôi đối với Làng đại học chính là những chuyến xe buýt, khi bạn chỉ cần đứng đợi vài phút là sẽ có một chuyến xe đưa bạn tới trường chỉ với 3 nghìn đồng.

Trong thế giới tương lai, những điểm đón xe buýt của Làng đại học được xếp thành một đường thẳng trên. Có \(n\) điểm đón xe buýt, và điểm thứ \(n + 1\) là trường Đại học Công nghệ thông tin (UIT). Xe buýt bắt đầu tại điểm đón thứ \(1\), đi lần lượt tới các điểm tiếp theo và kết thúc chuyến ở trường Đại học Công nghệ thông tin. Tại điểm đón thứ \(i\), sẽ có \(B_{i}\) sinh viên đón xe buýt ở đây, sinh viên thứ \(j\) trong \(B_{i}\) sinh viên này sẽ đợi xe buýt từ thời điểm \(T_{i, j}\). Từ điểm đón thứ \(i\) đi sang điểm đón thứ \(i + 1\), xe buýt sẽ mất \(A_{i}\) đơn vị thời gian để di chuyển.

Xe buýt này có \(M\) ghế ngồi, tới mỗi điểm đón xe buýt sẽ chọn dừng lại để chờ sinh viên (nếu còn chỗ ngồi) hoặc đi tiếp (hoặc chờ một chút rồi đi tiếp). Hỏi thời gian tối thiểu để xe buýt đi hết một lượt từ đầu tới cuối là bao nhiêu ? (lượt đi này phải đón đủ \(M\) học sinh hoặc đã đón hết tất cả học sinh).

Input

Dòng đầu tiên là hai số nguyên dương \(n\) và \(m\), lần lượt là số điểm đón và số ghế trên xe buýt. \((1 \leq n, m \leq 2 \times 10^5)\).

\(n\) dòng tiếp theo, mỗi dòng gồm hai số nguyên không âm \(A_{i}, B_{i}\). Tiếp sau đó là \(B_{i}\) số nguyên không âm \(T_{i, 1}, T_{i, 2}, ..., T_{i, b_{i}}\) \((A_{i}, T_{i, j} \leq 10^9)\).

Dữ liệu đảm bảo tổng số sinh viên chờ xe buýt không vượt quá \(2 \times 10^5\).

Output

Thời gian tối thiểu để đón \(M\) học sinh (hoặc đón tất cả các học sinh).

Example

4 5
2 2 1 3
2 3 1 2 3
4 2 12 19
3 2 10 7

12

3 6
2 2 1 2
4 3 4 8 9
4 3 11 8 9

15

Scoring

\begin itemize

• Có \(25\%\) số điểm có \(n, m \leq 20\) và tối đa \(20\) sinh viên chờ xe buýt.

• Có \(25\%\) số điểm có \(n, m \leq 2000\) và tổng số sinh viên chờ xe buýt không vượt quá \(2000\).

• Có \(25\%\) số điểm có \(A_{i}, T_{i, j} \leq 100, n \leq 1000\).

• \(25\%\) số điểm còn lại không có ràng buộc gì thêm.

\end itemize

Cho dãy số \(u_n\) được định nghĩa bởi công thức \(u_n = n^2 + 1\), với mọi số nguyên dương \(n \in \mathbb{N}^*\).

Với mỗi giá trị \(x\) cho trước, hãy tìm số nguyên dương \(n\) nhỏ nhất sao cho \(u_n \ge x\). Nói cách khác, bạn cần tìm giá trị đầu tiên của phần tử trong dãy \(u_n\) có giá trị nhỏ nhất lớn hơn hoặc bằng \(x\).

Input

Dữ liệu vào được cung cấp từ bàn phím theo định dạng sau:

• Dòng đầu tiên chứa một số nguyên dương \(N\) (\(N \le 10^6\)).
• Dòng thứ hai chứa một số nguyên dương \(T\) (\(T \le 10^5\)), biểu thị số lượng truy vấn.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(x\) (\(x \le u_n\)).

Output

Đối với mỗi truy vấn \(x\), in ra trên một dòng riêng biệt giá trị \(u_i\) tương ứng với số nguyên dương \(i\) nhỏ nhất sao cho \(u_i \ge x\).

Example

10
5
1
5
10
20
50

2
5
10
26
50

Trong mặt phẳng tọa độ Oxy, bạn được cho một tập hợp gồm \(n\) điểm. Nhiệm vụ của bạn là tìm khoảng cách Euclid ngắn nhất giữa hai điểm bất kỳ trong tập hợp đó.

Khoảng cách Euclid giữa hai điểm \((x_1, y_1)\) và \((x_2, y_2)\) được tính bằng công thức:

**Yêu cầu: **
Cho tọa độ của \(n\) điểm, hãy tìm khoảng cách Euclid ngắn nhất giữa hai điểm bất kỳ. Để đảm bảo kết quả là một số nguyên, bạn cần in ra bình phương của khoảng cách ngắn nhất này.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(2 \le n \le 2 \cdot 10^5\)), là số lượng điểm.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) (\(-10^9 \le x, y \le 10^9\)), là tọa độ của một điểm.
• Đảm bảo rằng không có hai điểm nào có cùng tọa độ.

Output

• In ra một số nguyên duy nhất là bình phương của khoảng cách Euclid ngắn nhất.

Example

4
2 1
4 4
1 2
6 3

2