Bài tập

Cho bốn số nguyên \(a, b, c, d\), trong đó ít nhất một số khác \(0\). Hãy tìm ước chung lớn nhất (một số nguyên dương) của cả bốn số.

Gợi ý: xây dựng hàm \(UCLN(a, b)\) tìm ước chung lớn nhất của hai số, rồi áp dụng liên tiếp.

Input

• Một dòng gồm bốn số nguyên \(a, b, c, d\) cách nhau bởi dấu cách.

Output

• In ra ước chung lớn nhất của bốn số.

Constraints

• \(|a|, |b|, |c|, |d| \le 10^{18}\)
• Có ít nhất một số khác \(0\).

Sample Input 1

12 18 30 48

Sample Output 1

6

Sample Input 2

-8 0 20 -12

Sample Output 2

4

Một tuyến xe điện có \(n\) điểm dừng đánh số từ \(1\) đến \(n\) theo thứ tự xe chạy. Tại điểm dừng \(i\) có \(a_i\) hành khách xuống xe và sau đó \(b_i\) hành khách lên xe (tất cả người xuống đều xuống trước khi có người lên). Xe trống khi đến điểm dừng đầu tiên, và ở điểm dừng cuối cùng mọi hành khách còn lại đều xuống hết, xe rỗng.

Hãy tính số ghế tối thiểu của xe để lúc nào mỗi hành khách cũng có ghế riêng, tức là số hành khách lớn nhất có trên xe tại một thời điểm.

Input

• Dòng đầu là số nguyên \(n\).
• \(n\) dòng sau, dòng thứ \(i\) gồm hai số nguyên \(a_i\) (số người xuống) và \(b_i\) (số người lên) tại điểm dừng \(i\).

Dữ liệu đảm bảo hợp lệ: \(a_1 = 0\), số người xuống không vượt quá số người đang trên xe, \(a_n\) bằng số người đang trên xe và \(b_n = 0\).

Output

• In ra số ghế tối thiểu cần có.

Constraints

• \(1 \le n \le 1000\)
• \(0 \le a_i, b_i \le 10^6\)

Sample Input

5
0 2
1 4
3 1
2 3
4 0

Sample Output

5

Explanation

Số người trên xe sau mỗi điểm dừng: \(2, 5, 3, 4, 0\). Lớn nhất là \(5\).

Một cửa hàng có \(n\) món đồ, món thứ \(i\) nặng \(w_i\) và có giá trị \(v_i\). Chiếc túi của bạn chịu được tổng khối lượng tối đa \(M\). Hãy chọn tập món (mỗi món tối đa một lần) sao cho tổng khối lượng không quá \(M\) và tổng giá trị lớn nhất, đồng thời in ra tập món được chọn.

Nếu có nhiều tập tối ưu, in tập có dãy chỉ số (xếp tăng dần) nhỏ nhất theo thứ tự từ điển.

Input

• Dòng đầu: hai số nguyên \(n\) và \(M\).
• \(n\) dòng tiếp: mỗi dòng hai số nguyên \(w_i\) và \(v_i\).

Output

• Dòng 1: số món được chọn.
• Dòng 2: chỉ số các món được chọn (đánh số từ 1 theo thứ tự nhập), tăng dần, cách nhau dấu cách.

Constraints

• \(1 \le n \le 24\)
• \(1 \le M \le 10^{11}\)
• \(1 \le w_i, v_i \le 10^9\)

Sample Input

5 15
6 4
4 5
7 8
3 2
5 6

Sample Output

3
3 4 5

Explanation

Tổng khối lượng \(7+3+5=15\), tổng giá trị \(16\) là lớn nhất.

Một cửa hàng có \(n\) món đồ, món thứ \(i\) nặng \(w_i\) và có giá trị \(v_i\). Bạn mang một chiếc túi chịu được tổng khối lượng tối đa \(M\). Chọn một số món (mỗi món tối đa một lần) sao cho tổng khối lượng không quá \(M\) và tổng giá trị lớn nhất.

Input

• Dòng đầu: hai số nguyên \(n\) và \(M\).
• \(n\) dòng tiếp: mỗi dòng hai số nguyên \(w_i\) và \(v_i\).

Output

• In ra tổng giá trị lớn nhất.

Constraints

• \(1 \le n \le 25\)
• \(1 \le M \le 10^{11}\)
• \(1 \le w_i, v_i \le 10^9\)

Sample Input

5 15
6 4
4 5
7 8
3 2
5 6

Sample Output

16

Explanation

Chọn món 3, 4, 5 (khối lượng \(7+3+5=15\), giá trị \(8+2+6=16\)).