USACO 2023 - Tháng 2 - Hạng Bạc

Bessie vừa mở một tiệm bánh!

Trong tiệm bánh của mình, Bessie có một lò nướng có thể làm một chiếc bánh quy trong \(t_C\) giây hoặc một chiếc bánh nướng xốp trong \(t_M\) giây \((1\leq t_C,t_M\leq10^9)\). Do hạn chế về không gian, Bessie chỉ có thể làm một chiếc bánh ngọt mỗi lần, vì vậy để làm \(A\) bánh quy và \(B\) bánh nướng xốp, phải mất \(A*t_C+B*t_M\) giây.

\(N(1 \leq N \leq 100)\) người bạn của Bessie muốn lần lượt tham quan tiệm bánh. Người bạn thứ \(i\) sẽ gọi \(a_i\) \((1 \leq a_i \leq 19^9)\) bánh quy và \(b_i(1 \leq b_i \leq 10^9)\) bánh nướng xốp ngay khi bước vào. Bessie không có chỗ để đựng bánh ngọt nên nó chỉ bắt đầu làm bánh ngọt khi nhận được đơn đặt hàng. Hơn nữa, bạn bè của Bessie rất bận rộn nên người bạn thứ \(i\) chỉ sẵn lòng đợi \(c_i(a_i+b_i<c_i<2*10^{18})\) giây, nếu không sẽ trở nên buồn bã và rời đi.

Bessie không muốn bạn bè mình phải buồn. Với một mặt trăng, nó có thể nâng cấp lò nướng của mình để giảm \(1\) giây làm một chiếc bánh quy hoặc giảm \(1\) giây làm một chiếc bánh nướng xốp. Nó chỉ có thể nâng cấp lò nướng trong một lượng số tự nhiên giây, và nó có thể nâng cấp lò nướng vô số lần trước khi bạn bè đến, miễn là thời gian cần thiết để làm bánh quy và bánh nướng xốp luôn dương

Với mỗi test \(T(1 \leq T \leq 100)\), hãy giúp Bessie tìm ra số mặt trăng tối thiểu mà Bessie phải bỏ ra để tiệm bánh của nó có thể làm hài lòng tất cả bạn bè.

Input

• Dòng đầu tiên chứa \(T\), số lượng test.
• Mỗi test bắt đầu bằng một dòng chứa \(N,t_C,t_M\). Sau đó, \(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a_i,b_i,c_i\).
• Các test liên tiếp cách nhau bởi dòng mới.

Output

Số lượng mặt trăng tối thiểu mà Bessie cần dành cho mỗi test trên các dòng riêng biệt.

Scoring

• Subtask \(1\): \(N \leq 10;t_c,t_m\leq1000\).
• Subtask \(2\): Không có điều kiện gì thêm.

Example

2
3 7 9
4 3 18
2 4 19
1 1 6
5 7 3
5 9 45
5 2 31
6 4 28
4 1 8
5 2 22

11
6

Ai đó đang chăn thả trong khu vườn riêng của nông dân John \((1 \leq G \leq 10^5)\)! Sử dụng kiến thức pháp y chuyên môn của mình, John đã có thể xác định thời gian chính xác khu vườn bị sử dụng. Ông cũng xác định rằng chỉ có một con bò chịu trách nhiệm cho sự việc trên.

Để đối phó với việc này, mỗi con bò \(N(1 \leq N \leq 10^5)\) của John đã cung cấp bằng chứng ngoại phạm chứng minh nó đã ở một địa điểm cụ thể vào một thời điểm cụ thể. Hãy giúp John kiểm tra xem mỗi bằng chứng ngoại phạm có chứng tỏ con bò đó vô tội hay không.

Một con bò được xác định là vô tội nếu bằng chứng ngoại phạm của nó cho thấy rằng nó không thể di chuyển giữa tất cả các bãi chăn thả. Bò di chuyển với tốc độ 1 đơn vị khoảng cách\(/1s\).

Input

• Dòng đầu tiên chứa hai số \(G\) và \(N\) cách nhau bởi dấu cách.
• \(G\) dòng tiếp theo chứa các số nguyên \(x,y\) và \(t(-10^9\leq x, y \leq 10^9; 0 \leq t \leq 10^9)\) được ngăn cách bởi dấu cách mô tả vị trí và thời gian chăn thả. Luôn có một con bò có thể di chuyển giữa tất cả các bãi chăn thả.
• \(N\) dòng tiếp theo chứa \(x,y\) và \(t(-10^9\leq x,y\leq 10^9;0\leq t\leq 10^9)\) ngăn cách bởi dấu cách mô tả vị trí và thời gian bằng chứng ngoại phạm của mỗi con bò.

Output

• In ra một số nguyên duy nhất: số con bò có bằng chứng ngoại phạm chứng minh nó vô tội.

Scoring

• Subtask \(1\): \(1\leq G,N \leq 10^3\), \(-10^6 \leq x,y \leq 10^6, 0\leq t \leq 10^6\)
• Subtask \(2\): Không có điều kiện gì thêm.

Example

2 4
0 0 100
50 0 200
0 50 50
1000 1000 0
50 0 200
10 0 170

2

Bessie đang đi nghỉ! Với một số tiến bộ công nghệ gần đây, Bessie sẽ đi bằng các chuyến bay có công nghệ cao, thậm chí có thể du hành thời gian. Hơn nữa, sẽ không có vấn đề gì nếu hai phiên bản "song song" của Bessie gặp nhau.

Trong nước có \(N\) sân bay được đánh số \(1,2,...,N\) và \(M\) chuyến bay du hành thời gian \((1 \leq N,M \leq 200000)\). Chuyến bay \(j\) rời sân bay \(c_j\) tại thời điểm \(r_j\), và đến sân bay \(d_j\) tại thời điểm \(s_j\) \((0 \leq r_j,s_j \leq 10^9)\). Ngoài ra, nó phải mất \(a_i\) thời gian cho việc quá cảnh tại sân bay \(i (1 \leq a_i \leq 10^9)\). (Nghĩa là, nếu Bessie đáp chuyến bay đến sân bay \(i\) tại thời điểm \(s\), thì nó có thể chuyển sang chuyến bay rời sân bay vào thời điểm \(r\) nếu \(s+a_i \leq r\). Việc quá cảnh không diễn ra khi Bessie đến sân bay.)

Bessie bắt đầu tại thành phố \(1\) vào lúc \(0\) . Đối với mỗi sân bay từ \(1\) đến \(N\), thời gian sớm nhất mà Bessie có thể đến đó là khi nào?

Input

• Dòng đầu tiên chứa N và M.
• \(M\) dòng tiếp theo mô tả các chuyến bay. Dòng thứ \(j\) trong số các dòng này chứa \(c_j\) , \(r_j\) , \(d_j\) , \(s_j\) theo thứ tự đó. \((1 \leq c_j,d_j \leq N, 0 \leq r_j,s_j \leq 10^9 )\)
• Dòng tiếp theo mô tả các sân bay. Nó chứa \(N\) số nguyên cách nhau bằng dấu cách \(a_1,…,a_N\).

Output

In ra \(N\) dòng, dòng thứ \(i\) chứa thời gian sớm nhất Bessie có thể đến sân bay \(i\), hoặc \(-1\) nếu Bessie không thể đến sân bay đó.

Scoring

• Subtask \(1\): \(r_j<s_j\) cho tất cả \(j\), tức là tất cả các chuyến bay đều đến sau khi chúng khởi hành.
• Subtask \(2\): \(N,M \leq 5000\)
• Subtask \(3\): Không có điều kiện gì thêm.

Example

3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 10

0
0
20

3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 10

0
10
-1