Tại Fontaine hôm nay đang diễn ra rất nhiều sự kiện xung quanh Oratrice Mécanique d'Analyse Cardinale và Charlotte là tay nhiếp ảnh chuyên nghiệp của tòa soạn báo tại Fontaine được giao nhiêm vụ đi chụp ảnh ở đó. Khu vực tại Oratrice Mécanique d'Analyse Cardinale có chiều dài là ~L~ và có tổng cộng ~N~ sự kiện được tổ chức, sự kiện thứ ~i~ có mã sự kiện là ~c_i~ tổ chức tại vị trí ~x_i~. Charlotte có một chiếc máy ảnh với tiêu cự ~delta~, với mỗi lần chụp ảnh tại vị trí ~x~ thì bức ảnh cô có được sẽ có hình từ vị trí ~[x - delta, x + delta]~

Charlotte muốn biết được mình có thể chụp nhiều nhất là bao nhiêu sự kiện tại Oratrice Mécanique d'Analyse Cardinale. Hãy giúp Charlotte tính toán

Input

Dòng đầu tiên gồm 3 số nguyên ~N~, ~L~ và ~delta~: số sự kiện, chiều dài của Oratrice Mécanique d'Analyse Cardinale và tiêu cự máy ảnh của Charlotte

~N~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~c_i~ và ~x_i~, loại sự kiện và vị trí của sự kiện thứ ~i~

Output

Số sự kiện nhiều nhất mà Charlotte có thể có trong một bức ảnh

Giới hạn

~1 <= N <= 10^5~

~1 <= delta, L <= 10^9~

~1 <= x_i <= L~

Test mẫu

Input

7 8 2
1 1
2 2
2 3
2 4
3 5
4 7
5 8

Output

4

Furina là vị thẩn (ahem) tại vùng đất Fontaine, cô được đối xử như một ngôi sao tại đất nước của mình. Các phiên xét xử của cô tại Oratrice Mecanique d'Analyse Cardinale luôn đắt vé, song Furina lại có một cuộc sống khá giản dị.

Một buổi xét xử của Furina có ~N~ vé, giá của vé ~i~ là ~p_i~. Ban tổ chức có quyền sắp xếp vé nào sẽ được bán trước. Tiền bán vé sẽ được trích một phần để gửi cho Furina theo 2 cách:

• ~x\%~ của giá vé thứ ~a, 2a, ...~
• ~y\%~ của giá vé thứ ~b, 2b, ...~
• Nếu vé đó là bội của cả ~a~ và ~b~ thì sẽ trích ra cả 2 tiêu chí trên (~x+y%~)

Ví dụ, nếu có 4 vé [400, 100, 200, 300], và cứ 2 vé thì trích ra 10%, 3 vé thì trích 20%, thì bán theo thứ tự [100, 200, 400, 300] sẽ trích ra từ các vé lần lượt [0, 20, 80, 30] tổng là 130 đồng

Furina nhờ bạn có thể tính xem sẽ phải bán ít nhất bao nhiêu vé để cô có thể trả tiền thuê nhà là ~S~ tại trung tâm Fontaine tháng này ᗜˬᗜ

Input

Dòng đầu tiên gồm 2 số nguyên ~N~ và ~S~, số vé của buổi xét xử và tiền thuê nhà của Furina

Dòng thứ 2 gồm 4 số nguyên ~a, x, b, y~: phần trích ra sau khi bán được vé.

Dòng thứ 3 gồm ~N~ số nguyên: giá bán các vé trong sự kiện.

Giá vé đảm bảo chia hết cho 100

Output

In ra một số nguyên là số vé mà Furina cần bán để trả tiền thuê nhà, nếu Furina không đủ sức trả thì in ra "ᗜˬᗜ".

Giới hạn

~1 <= N <= 2*10^5~

~1 <= S <= 10^{12}~

~1 <= x, y <= 100, x + y <= 100~

~1 <= a, b <= N~

~1 <= p_i <= 10^{12}~

Test mẫu

Input

8 110
2 10 3 15
100 200 100 200 100 200 100 100

Output

6

Input

1 100
1 50 1 49
100

Output

ᗜˬᗜ

Trò chơi Genius Invocation TCG được tạo ra ở Mondstadt đã có sức ảnh hưởng lan rộng tới Fontaine, và giờ ai cũng nói đến nó. Navia và Clorinde hôm nay đã thử thách bạn với một ván GI TCG. Tuy nhiên, luật chơi của game này khác một chút so với GI TCG thông thường.

Bạn đang ở phiên đánh boss cùng Navia và Clorinde. Trận đánh kéo dài ~N~ lượt. Với mỗi một turn, bạn sẽ nhận được một số lá bài. Mỗi lá có 2 chỉ sổ: ~c_i~ chi phí của nó và ~d_i~ sát thương nó gây ra. Trong một turn, bạn có thể chơi một số lá bài của mình theo một thứ tự do bạn chọn, sao cho tổng chi phí của các lá bài bạn chơi không vượt quá 3. Sau khi chơi (có thể là không lá nào) các lá bài, bạn sẽ kết thúc lượt và tất cả những lá bài không được chơi sẽ bị hủy bỏ.

Navia và Clorinde cũng cung cấp cho bạn một buff nhỏ trong trận đánh: mỗi lá bài thứ 10 gây gấp đôi sát thương.

Vậy sau ~N~ turn, lượng sát thương lớn nhất mà bạn có thể gây ra là bao nhiêu

Input

Dòng đầu tiên gồm một số nguyên ~N~: số lượt của trận đánh

~N~ cụm dòng tiếp theo, cụm thứ ~i~ biểu diện các lá bài bạn sẽ nhận được vào lượt thứ ~i~

Dòng đầu tiên của một cụm chứa số nguyên ~K~, số lá bài mà bạn nhận được trong lượt

~K~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~c_i~ và ~d_i~ là chỉ số của các lá bài

Output

In ra lượng sát thương lớn nhất mà bạn có thể gây ra

Giới hạn

~1 <= N <= 2*10^5~

~1 <= K <= 2*10^5~

~1 <= c_i <= 3~

~1 <= d_i <= 10^9~

Đảm bảo tổng số lá bài phải xử lý trong bộ test là ít hơn ~2*10^5~

Test mẫu

Input

5
3
1 6
1 7
1 5
2
1 4
1 3
3
1 10
3 5
2 3
3
1 15
2 4
1 10
1
1 100

Output

263

Cho một đồ thị có hướng gồm ~N~ đỉnh và ~M~ cạnh, cho một số nguyên ~K~.

Hãy tìm số cách di chuyển từ đỉnh 1 đến đỉnh ~N~ sao cho đường đi đó chứa đúng ~K~ cạnh

Input

Dòng thứ nhất gồm ba số nguyên ~N~, ~M~, ~K~, số đỉnh, số cạnh và độ dài đường đi ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~ mô tả cạnh nối từ đỉnh ~u~ đến đỉnh ~v~

Output

Gồm một số nguyên là số cách đi từ 1 đến ~N~ modulo ~10^9+7~

Giới hạn

~1 <= N <= 100~

~1 <= M <= N*(N-1)~

~1 <= K <= 10^9~

~1 <= u, v <= N~

Test mẫu

Input

3 4 8
1 2
2 3
3 1
3 2

Output

2

Cho một lưới ô vuông đơn vị kích thước m × n. Các hàng của lưới được đánh số từ 1 tới m từ trên xuống và các cột của lưới được đánh số từ 1 tới n từ trái qua phải. Ô nằm trên giao điểm của hàng i và cột j được gọi là ô (i,j). Có một con xúc xắc nằm ở ô (1,1). Các mặt của con xúc xắc được ghi một số tự nhiên từ 1 tới 6: Mặt áp xuống lưới mang số 6, mặt hướng về mép trên của lưới mang số 2, mặt hướng về mép trái của lưới mang số 3, tổng 2 số ghi trên 2 mặt đối diện bất kỳ luôn bằng 7 (xem hình vẽ). Khi con xúc xắc lăn sang một trong 4 ô kề cạnh (không được lăn ra khỏi lưới), mặt trên của xúc xắc sẽ trở thành mặt bên tương ứng với hướng di chuyển và mặt bên theo hướng di chuyển sẽ trở thành mặt đáy. Sau mỗi phép lăn, số trên mặt đáy của quân xúc xắc sẽ in lên ô mà quân xúc xắc vừa mới lăn sang. Ban đầu xúc xắc in số 6 lên ô (1,1).

Đầu tiên quân xúc xắc lăn sang phải tới một ô ở mép phải của lưới, sau đó nó lăn xuống hàng dưới rồi tiếp tục lăn sang trái tới một ô ở mép trái của lưới, sau đó nó lại lăn xuống hàng dưới nữa và quá trình tiếp tục như vậy cho tới khi mọi ô của lưới đã được quân xúc xắc lăn qua và in số.

Tính tổng các số ghi trên lưới sau khi quân xúc xắc lăn qua theo luật trên

Input

Dòng đầu tiền gồm 2 số nguyên dương ~m, n~

Output

Một số nguyên là tổng của các số có trên lưới sau khi lăn xúc xắc

Giới hạn

~1 <= m, n <= 10^9~

Test mẫu

Input

4 4

Output

56

Giải thích: http://pasteboard.co/SUp03rtGPvkL.png

Bạn có ~N~ hình chữ nhật trên mặt phẳng với hệ tọa độ trực chuẩn Οxy, mỗi hình được mô tả bởi ba số nguyên ~(i,j, k)~. Trong đó góc dưới bên trái của hình chữ nhật sẽ nằm ở điểm ~(i, 0)~ và góc trên bên phải của hình chữ nhật sẽ nằm ở điểm ~(j, k)~.

Tính diện tích phần mặt phẳng bị các hình chữ nhật chiếm chỗ

Input

Dòng 1 chứa số nguyên dương ~N~

~N~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~i~, ~j~, ~k~ xác định một hình chữ nhật

Output

Một số nguyên duy nhất là diện tích phần mặt phẳng bị các hình chữ nhật chiếm chỗ

Giới hạn

~1 <= N <= 10^5~

~0 <= i < j <= 10^6~

~1 <= K <= 10^6~

Test mẫu

Input

3
0 2 3
1 4 4
1 5 2

Output

17