Táo của bà Lan

Bà Lan mang một số táo ra chợ bán và đến cuối ngày thì bán hết sạch. Bà không còn nhớ ban đầu mình mang bao nhiêu quả táo, nhưng bà nhớ chính xác rằng đã có $n$ người mua, và mỗi người mua đúng một nửa số táo mà bà đang có tại thời điểm đó. Ngoài ra, nếu tại thời điểm mua số táo đang có là số lẻ, bà tặng thêm cho người mua nửa quả táo nữa.

Như vậy mỗi người mua luôn nhận về một số nguyên dương quả táo, nhưng có thể người đó không phải trả tiền cho nửa quả táo được tặng.

Với mỗi người mua, bà Lan nhớ được mình có tặng thêm nửa quả táo hay không. Giá của một quả táo là $p$ (số $p$ là số chẵn).

Hãy tính tổng số tiền bà Lan đáng lẽ phải thu được vào cuối ngày, để bà kiểm tra xem có người mua nào lừa bà không.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $p$: số người mua và giá một quả táo.
• $n$ dòng tiếp theo mô tả từng người mua theo thứ tự: xâu half nếu người đó chỉ mua một nửa số táo, hoặc xâu halfplus nếu bà Lan còn tặng thêm nửa quả táo.

Dữ liệu đảm bảo ban đầu bà Lan có ít nhất một quả táo và cuối ngày bà không còn quả nào.

Dữ liệu ra

Một số nguyên duy nhất: tổng số tiền bà Lan phải thu được. Kết quả có thể rất lớn, hãy dùng kiểu số nguyên 64 bit.

Ràng buộc

• $1\le n\le 40$
• $2\le p\le 1000$, $p$ chẵn

Ví dụ